Author Topic: fibonacci(4784969)  (Read 36997 times)

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: fibonacci(4784969)
« Reply #60 on: June 15, 2019, 04:30:10 PM »
I was wondering how porting the fib2 function I posted previously to a more native SB code base would look/work:
Code: ScriptBasic
  1. import gmp2.bas
  2.  
  3. n = 4784969
  4. count = n
  5.  
  6. a = gmp2::init_set(1)
  7. b = gmp2::init_set(0)
  8. p = gmp2::init_set(0)
  9. q = gmp2::init_set(1)
  10.  
  11. psq = gmp2::init()
  12. qsq = gmp2::init()
  13. twopq = gmp2::init()
  14. bq = gmp2::init()
  15. aq = gmp2::init()
  16. ap = gmp2::init()
  17. bp = gmp2::init()
  18.  
  19. while count > 0
  20.     if (count % 2) = 0 then
  21.         psq = gmp2::mul(p, p)
  22.         qsq = gmp2::mul(q, q)
  23.         twopq = gmp2::mul(p, q)
  24.         twopq = gmp2::mul_si(twopq, 2)
  25.  
  26.         p = gmp2::add(psq, qsq)
  27.         q = gmp2::add(twopq, qsq)
  28.  
  29.         count = count / 2
  30.     else
  31.         bq = gmp2::mul(b, q)
  32.         aq = gmp2::mul(a, q)
  33.         ap = gmp2::mul(a, p)
  34.         bp = gmp2::mul(b, p)
  35.  
  36.         a = gmp2::add(bq, aq)
  37.         a = gmp2::add(a, ap)
  38.  
  39.         b = gmp2::add(bp, aq)
  40.  
  41.         count = count - 1
  42.  
  43.     end if
  44.  
  45. wend
  46. print b,"\n"

On my RasPi:

riveraa@dpi:~/sb $ time ./AppRun newfib.sb >fib.txt

real    0m38.965s
user    0m38.733s
sys    0m0.224s


On my Mac Mini:
[riveraa@mini ~/sb] $ time ./AppRun newfib.sb >fib.txt

real    0m3.159s
user    0m3.094s
sys    0m0.051s


Module Source:
Code: C
  1. /*
  2. READ THIS FILE AND CHANGE THE SOURCE WHEREVER YOU SEE COMMENTS STARTING
  3. WITH THE WORD *TODO*
  4.  
  5. WHEN YOU ARE FINISHED YOU CAN
  6.  
  7.   FILE   : interface.c
  8.   HEADER : interface.h
  9.   BAS    : gmp2.bas
  10.   AUTHOR : *TODO*
  11.  
  12.   DATE:
  13.  
  14.   CONTENT:
  15.   This is the interface.c file for the ScriptBasic module gmp2
  16. ----------------------------------------------------------------------------
  17.  
  18. Remove the two characters // from following line(s) if this module is supposed to
  19. be compiled under specific OS's. If there is a need for some library to successfully
  20. compile the module under Windows specify the names of the libraries on the line
  21. as it is listed for the linker application. This is usually something like
  22.  
  23. WINDOWS: libname1.lib libname2.lib ... libnameX.lib
  24. LINUX/MACOS: -lm -ldl
  25.  
  26. If there are no libraries, but still the module is to be compiled under Windows
  27. do remove the // characters so that the program setup.pl will know that the
  28. module is meant for Windows.
  29.  
  30. //NTLIBS:
  31. UXLIBS: -lgmp
  32. DWLIBS: -lgmp -macosx_version_min 10.12
  33.  
  34. */
  35.  
  36. /*
  37. *TODO*
  38. INCLUDE HERE THE SYSTEM HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
  39. */
  40.  
  41. #ifdef WIN32
  42. /*
  43. *TODO*
  44. INCLUDE HERE THE WIN32 SPECIFIC HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
  45. */
  46. #else
  47. /*
  48. *TODO*
  49. INCLUDE HERE THE UNIX SPECIFIC HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
  50. */
  51. #endif
  52.  
  53. /*
  54. *TODO*
  55. INCLUDE HERE THE LOCAL HEADER FILES THAT ARE NEEDED TO COMPILE THIS MODULE
  56. */
  57. #include <stdio.h>
  58. #include <stdlib.h>
  59. #include <string.h>
  60. #include "../../basext.h"
  61. #include <gmp.h>
  62.  
  63. /*
  64. *TODO*
  65. INSERT THE BASIC CODE THAT WILL GET INTO THE FILE gmp2.BAS
  66. AFTER THE LINE 'TO_BAS:' AND BEFORE THE LINE END OF THE COMMENT
  67.  
  68. NOTE THAT SUB AND COMMAND DECLARATIONS ARE CREATED AUTOMATICALLY
  69. FROM THE FUNCTION DEFINTIONS WHEN THE MODULE IS CONFIGURED BEFORE
  70. COMPILATION
  71.  
  72. TO_BAS:
  73. */
  74.  
  75. /*
  76. *TODO*
  77. DECLARE HERE THE MODULE OBJECT TYPE. THIS STRUCTURE SHOULD HOLD THE
  78. DATA AVAILABLE FOR EACH INTERPRETER THREAD. USE THIS STRUCTURE TO
  79. STORE GLOBAL VALUES INSTEAD OF USING GLOBAL VARIABLES.
  80. */
  81. typedef struct _ModuleObject {
  82.   char a; /* You may delete this. It is here to make the initial interface.c compilable. */
  83.   }ModuleObject,*pModuleObject;
  84.  
  85. mpz_t g_Op1, g_Op2, g_Res;
  86.  
  87. /*
  88. *TODO*
  89. ALTER THE VERSION NEGOTIATION CODE IF YOU NEED
  90. */
  91. besVERSION_NEGOTIATE
  92.   return (int)INTERFACE_VERSION;
  93. besEND
  94.  
  95. /*
  96. *TODO*
  97. ALTER THE ERROR MESSAGE FUNCTION
  98. */
  99. besSUB_ERRMSG
  100.  
  101.   switch( iError ){
  102.     case 0x00080000: return "ERROR HAS HAPPENED";
  103.     }
  104.   return "Unknown gmp2 module error.";
  105. besEND
  106.  
  107. /*
  108. *TODO*
  109. ALTER THE MODULE INITIALIZATION CODE
  110. */
  111. besSUB_START
  112.   pModuleObject p;
  113.  
  114.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
  115.   if( besMODULEPOINTER == NULL )return 0;
  116.  
  117.   mpz_init(g_Op1);
  118.   mpz_init(g_Op2);
  119.   mpz_init(g_Res);
  120.  
  121. /*
  122. *TODO*
  123. INSERT HERE ANY CODE THAT YOU NEED TO INITIALIZE THE MODULE FOR THE
  124. ACTUAL INTERPRETER THREAD
  125. */
  126.  
  127. besEND
  128.  
  129. /*
  130. *TODO*
  131. ALTER THE MODULE FINISH CODE IF NEEDED
  132. */
  133. besSUB_FINISH
  134.   pModuleObject p;
  135.  
  136.   /*
  137.     YOU CERTAINLY NEED THIS POINTER TO FREE ALL RESOURCES THAT YOU ALLOCATED
  138.     YOU NEED NOT CALL besFREE TO FREE THE MEMORY ALLOCATED USING besALLOC
  139.     CLOSE ANY FILE THAT REMAINED OPEN, RELEASE DATABASE HANDLES AND ALL
  140.     OTHER RESOURCES INCLUDING MEMORY *NOT* ALLOCATED CALLING besALLOC
  141.   */
  142.   p = (pModuleObject)besMODULEPOINTER;
  143.   if( p == NULL )return 0;
  144.  
  145.   return 0;
  146. besEND
  147.  
  148.  
  149. /*
  150. *TODO*
  151. WRITE YOUR MODULE INTERFACE FUNCTIONS FOLLOWING THIS SKELETON
  152.  
  153. NOTE THAT THIS IS A SAMPLE FUNCTION, YOU CAN ALSO DELETE
  154. LINES FROM IT IF NEEDED
  155. */
  156. /**
  157. =section mpz
  158. =H mpz
  159.  
  160. Returns new mpz_t object
  161. */
  162. besFUNCTION(mpz)
  163.   pModuleObject p;
  164.   mpz_t r;
  165.  
  166.   p = (pModuleObject)besMODULEPOINTER;
  167.  
  168.   // besARGUMENTS("i[s]")
  169.   //   &r
  170.   // besARGEND
  171.  
  172.   besRETURN_POINTER(r);
  173. besEND
  174.  
  175. /**
  176. =section init
  177. =H mpz
  178.  
  179. Initializes mpz_t object
  180. */
  181. besFUNCTION(init)
  182.   pModuleObject p;
  183.   mpz_t r;
  184.   char * res;
  185.  
  186.   p = (pModuleObject)besMODULEPOINTER;
  187.  
  188.   // besARGUMENTS("p")
  189.   //   &r
  190.   // besARGEND
  191.  
  192.   mpz_init(r);
  193.   res = mpz_get_str(NULL,10,r);
  194.   besSET_RETURN_STRING(res);
  195.   free(res);
  196.  
  197.   besRETURN_POINTER(r);
  198. besEND
  199.  
  200.  
  201. /**
  202. =section init_set
  203. =H mpz
  204.  
  205. Initializes mpz_t object
  206. */
  207. besFUNCTION(init_set)
  208.   pModuleObject p;
  209.   char *s, *res;
  210.   int i;
  211.  
  212.   p = (pModuleObject)besMODULEPOINTER;
  213.  
  214.   besARGUMENTS("z")
  215.     &s
  216.   besARGEND
  217.  
  218.   // mpz_set_str(g_Op1, s, 10);
  219.   mpz_init_set_str(g_Res,s,10);
  220.   res = mpz_get_str(NULL,10,g_Res);
  221.   besSET_RETURN_STRING(res);
  222.   free(res);
  223. besEND
  224.  
  225. /**
  226. =section mul
  227. =H mpz
  228.  
  229. Multiplies mpz_t objects
  230. */
  231. besFUNCTION(mul)
  232.   pModuleObject p;
  233.   char *s, *t, *res;
  234.   int i;
  235.  
  236.   p = (pModuleObject)besMODULEPOINTER;
  237.  
  238.   besARGUMENTS("zz")
  239.     &s,&t
  240.   besARGEND
  241.  
  242.  mpz_set_str(g_Op1, s, 10);
  243.  mpz_set_str(g_Op2, t, 10);
  244.   mpz_mul(g_Res, g_Op1, g_Op2);
  245.   res = mpz_get_str(NULL,10,g_Res);
  246.   besSET_RETURN_STRING(res);
  247.   free(res);
  248. besEND
  249.  
  250.  
  251. /**
  252. =section mul_si
  253. =H mpz
  254.  
  255. Multiplies mpz_t objects
  256. */
  257. besFUNCTION(mul_si)
  258.   pModuleObject p;
  259.   char *s,*res;
  260.   long i;
  261.  
  262.   p = (pModuleObject)besMODULEPOINTER;
  263.  
  264.   besARGUMENTS("zi")
  265.     &s,&i
  266.   besARGEND
  267.  
  268.   mpz_set_str(g_Op1, s, 10);
  269.   mpz_mul_si(g_Res, g_Op1, i);
  270.  
  271.   res = mpz_get_str(NULL,10,g_Res);
  272.   besSET_RETURN_STRING(res);
  273.   free(res);
  274. besEND
  275.  
  276.  
  277. /**
  278. =section add
  279. =H add
  280.  
  281. Adds mpz_t objects
  282. */
  283. besFUNCTION(add)
  284.   pModuleObject p;
  285.   char *s, *t, *res;
  286.  
  287.   int i;
  288.  
  289.   p = (pModuleObject)besMODULEPOINTER;
  290.  
  291.   besARGUMENTS("zz")
  292.     &s,&t
  293.   besARGEND
  294.  
  295.   mpz_set_str(g_Op1, s, 10);
  296.   mpz_set_str(g_Op2, t, 10);
  297.   mpz_add(g_Res, g_Op1, g_Op2);
  298.  
  299.   res = mpz_get_str(NULL,10,g_Res);
  300.   besSET_RETURN_STRING(res);
  301.   free(res);
  302. besEND
  303.  
  304.  
  305. /**
  306. =section test
  307. =H add
  308.  
  309. Adds mpz_t objects
  310. */
  311. besFUNCTION(test)
  312.   pModuleObject p;
  313.   mpz_t r, s, t;
  314.   int i;
  315.  
  316.   p = (pModuleObject)besMODULEPOINTER;
  317.  
  318.   // besARGUMENTS("ppp")
  319.   //   &r,&s,&t
  320.   // besARGEND
  321.  
  322.   // mpz_add(r, s, t);
  323.   i=12345;
  324.  
  325.   besRETURN_LONG(i);
  326. besEND
  327.  
  328. /**
  329. =section get_string
  330. =H add
  331.  
  332. Adds mpz_t objects
  333. */
  334. besFUNCTION(get_string)
  335.   pModuleObject p;
  336.   mpz_t r, s, t;
  337.   int i;
  338.   char * retstring;
  339.  
  340.   p = (pModuleObject)besMODULEPOINTER;
  341.  
  342.   besARGUMENTS("p")
  343.     &r
  344.   besARGEND
  345.  
  346.   retstring = mpz_get_str(0,10,r);
  347.  
  348.   besSET_RETURN_STRING(retstring);
  349.   free(retstring);
  350. besEND
  351.  
  352. /*
  353. *TODO*
  354. INSERT HERE THE NAME OF THE FUNCTION AND THE FUNCTION INTO THE
  355. TABLE. THIS TABLE IS USED TO FIND THE FUNCTIONS WHEN THE MODULE
  356. INTERFACE FILE IS COMPILED.
  357. */
  358.  
  359. SLFST GMP2_SLFST[] ={
  360.  
  361. { "versmodu" , versmodu },
  362. { "bootmodu" , bootmodu },
  363. { "finimodu" , finimodu },
  364. { "emsgmodu" , emsgmodu },
  365. { "mpz" , mpz },
  366. { "init" , init },
  367. { "init_set" , init_set },
  368. { "mul" , mul },
  369. { "mul_si" , mul_si },
  370. { "add" , add },
  371. { "get_string" , get_string },
  372. { NULL , NULL }
  373.   };

AIR.



Offline John

  • Forum Support / SB Dev
  • Posts: 3597
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #61 on: June 15, 2019, 05:15:11 PM »
Can you include subtraction, divide standard and integer divide to your library and we can make that the ScriptBasic official GMP extension module.

Nice Job!

Your GMP2 fibo ran in 4.7 seconds on my laptop. Heater's recursive version took 1 minute 9 seconds using the GMP we worked together on.
« Last Edit: June 15, 2019, 07:01:41 PM by John »

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: fibonacci(4784969)
« Reply #62 on: June 15, 2019, 07:00:59 PM »
Added sub and divide functions.  Anything else, look at how I did the functions and adapt to your needs.

Pushed up to sandbox.

Code: ScriptBasic
  1. Import gmp2.bas
  2.  
  3. a = gmp2::sub(1000000,500000)
  4.  
  5. print a,"\n"
  6.  
  7. b = gmp2::divide(a,5)
  8.  
  9. print b,"\n"

[riveraa@mini ~/sb] $ ./sb math.sb
500000
100000


AIR.

Offline John

  • Forum Support / SB Dev
  • Posts: 3597
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #63 on: June 15, 2019, 07:05:24 PM »
Outstanding!

Now Heater will push the ScriptBasic submission to the official Fibonacci 1 million digit challenge repo.

I think we are safe so you can return to being Clark Kent.  :-*

I'm surprized SB is allowing us to use the SUB keyword as a user function.
« Last Edit: June 15, 2019, 07:25:46 PM by John »

Offline John

  • Forum Support / SB Dev
  • Posts: 3597
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #64 on: June 15, 2019, 08:05:28 PM »
I noticed in your Sub / Divide example you didn't init any of the variables. When is it required?

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: fibonacci(4784969)
« Reply #65 on: June 15, 2019, 08:14:27 PM »
Really only needed if calling functions where you pass them.


Since the module functions are returning strings, SB rules apply. You only need to init the vars if they will be passed to a function at some point.


I think you can even just init them as empty strings directly, since that is what is returned from the init function.


Play with it and see.

Offline John

  • Forum Support / SB Dev
  • Posts: 3597
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #66 on: June 15, 2019, 08:26:58 PM »
In you example a is passed to the GMP2 function. In the previous call you pass constants. Does a returned variable from GMP2 auto init the variable?

You are setting the string in each of the operator calls like I did but made it a static function. I don't see the auto clear though.

Code: C
  1. besFUNCTION(add)
  2.   pModuleObject p;
  3.   char *s, *t, *res;
  4.  
  5.   int i;
  6.  
  7.   p = (pModuleObject)besMODULEPOINTER;
  8.  
  9.   besARGUMENTS("zz")
  10.     &s,&t
  11.   besARGEND
  12.  
  13.   mpz_set_str(g_Op1, s, 10);
  14.   mpz_set_str(g_Op2, t, 10);
  15.   mpz_add(g_Res, g_Op1, g_Op2);
  16.  
  17.   res = mpz_get_str(NULL,10,g_Res);
  18.   besSET_RETURN_STRING(res);
  19.   free(res);
  20. besEND
  21.  
« Last Edit: June 15, 2019, 08:37:12 PM by John »

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: fibonacci(4784969)
« Reply #67 on: June 15, 2019, 08:36:34 PM »
The functions return strings.  Look at the code and you'll see that it's similar to what you were trying.

Offline John

  • Forum Support / SB Dev
  • Posts: 3597
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #68 on: June 15, 2019, 08:44:28 PM »
Here is what my ADD looks like. This way I never have to worry about initializing and clearing the GMP string objects.

Code: C
  1. besFUNCTION(bi_add)
  2.   const char* s1;
  3.   const char* s2;
  4.  
  5.   besARGUMENTS("zz")
  6.     &s1, &s2
  7.   besARGEND
  8.  
  9.   gmp_init();
  10.   mpz_set_str(op1, s1, 10);
  11.   mpz_set_str(op2, s2, 10);
  12.  
  13.   mpz_add(res, op1, op2);
  14.   char* res_string = mpz_get_str (0, 10, res);
  15.   besSET_RETURN_STRING(res_string);
  16.   gmp_clear();
  17.   free(res_string);
  18.  
  19. besEND
  20.  
« Last Edit: June 15, 2019, 08:47:13 PM by John »

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: fibonacci(4784969)
« Reply #69 on: June 15, 2019, 09:02:32 PM »
Code: C
  1. besSUB_START
  2.   pModuleObject p;
  3.  
  4.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
  5.   if( besMODULEPOINTER == NULL )return 0;
  6.  
  7.   mpz_init(g_Op1);
  8.   mpz_init(g_Op2);
  9.   mpz_init(g_Res);
  10.  
  11. besEND

Code: C
  1. besSUB_FINISH
  2.   pModuleObject p;
  3.  
  4.   p = (pModuleObject)besMODULEPOINTER;
  5.   if( p == NULL )return 0;
  6.   mpz_clear(g_Op1);
  7.   mpz_clear(g_Op2);
  8.   mpz_clear(g_Res);
  9.   return 0;
  10. besEND

Your approach introduces additional overhead to init/clear/int/clear/etc.

Using SB's Module support functions, I only have to init/clear once.  Init when the module is loaded, and clear when the module exits.  3 inits/clears, vs init * number of functions and clear * number of functions.

If you look at what's happening, you are init'ing the variables, then immediately setting them.  Then you clear them, so it's like wash/rinse/repeat.  Each init/clear call you make is taking additional time that isn't necessary.

With my approach, I init once and set the variables each time I need to.  Then when the module is unloaded, the resources I init'd are released.  Once I set that in the Module, I don't have to remember to do it in each function I implement.


AIR.

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: fibonacci(4784969)
« Reply #70 on: June 15, 2019, 09:08:44 PM »
In response to your question about setting the variables in an SB script with the GMP2 module:
Code: ScriptBasic
  1. a = 1
  2. b = 0
  3. p = 0
  4. q = 1
  5.  
  6. psq = 0
  7. qsq = 0
  8. twopq = 0
  9. bq = 0
  10. aq = 0
  11. ap = 0
  12. bp = 0

This still works as expected, so the calls to GMP2::init() aren't necessary...

AIR.

Offline John

  • Forum Support / SB Dev
  • Posts: 3597
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #71 on: June 15, 2019, 09:09:38 PM »
I missed the code in the START / FINISH SB routines.

I will do some testing and see if anything crops up.

Offline John

  • Forum Support / SB Dev
  • Posts: 3597
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #72 on: June 15, 2019, 09:12:35 PM »
That's great. Is the set not need as well?

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: fibonacci(4784969)
« Reply #73 on: June 15, 2019, 09:13:35 PM »
Code: ScriptBasic
  1. import gmp2.bas
  2.  
  3. count = 4784969
  4.  
  5. a = 1
  6. b = 0
  7. p = 0
  8. q = 1
  9.  
  10.  
  11. while count > 0
  12.     if (count % 2) = 0 then
  13.         psq = gmp2::mul(p, p)
  14.         qsq = gmp2::mul(q, q)
  15.         twopq = gmp2::mul(p, q)
  16.         twopq = gmp2::mul_si(twopq, 2)
  17.  
  18.         p = gmp2::add(psq, qsq)
  19.         q = gmp2::add(twopq, qsq)
  20.  
  21.         count = count / 2
  22.     else
  23.         bq = gmp2::mul(b, q)
  24.         aq = gmp2::mul(a, q)
  25.         ap = gmp2::mul(a, p)
  26.         bp = gmp2::mul(b, p)
  27.  
  28.         a = gmp2::add(bq, aq)
  29.         a = gmp2::add(a, ap)
  30.  
  31.         b = gmp2::add(bp, aq)
  32.  
  33.         count = count - 1
  34.  
  35.     end if
  36.  
  37. wend
  38. print b,"\n"

This is all you need, in this case.  The other vars are created within the WHILE loop.

AIR.

Offline AIR

  • BASIC Developer
  • Posts: 932
  • Coder
Re: fibonacci(4784969)
« Reply #74 on: June 15, 2019, 10:36:54 PM »
Factorial(100) example:
Code: ScriptBasic
  1. Import gmp2.bas
  2.  
  3. n = 100
  4. fact = 1
  5.  
  6. while n > 1
  7.     fact = gmp2::mul(fact,n)
  8.     n -=1
  9. wend
  10.  
  11. print fact,"\n"

[riveraa@mini ~/sb] $ ./sb factorial.sb
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000


I know it's off-topic, but wanted to show how GMP makes handling large numbers easy.

AIR.