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

Offline AIR

  • BASIC Developer
  • Posts: 684
Re: fibonacci(4784969)
« Reply #45 on: June 12, 2019, 10:00:21 AM »
As far as the buffer:
Code: C
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int main(int argc, char **argv) {
  6.     char buf[atoi(argv[1])+1];
  7.     memset(buf,0,1);
  8.     printf("%lu\n",sizeof(buf));
  9.     return 0;
  10. }

Compile it, and pass it a number when you run it (it will segfault if you don't pass a number.  No error checking in this example).  It will output the size of the buffer.

So if you pass 4784969, the size of the buffer will be 4,784,970 bytes.  A bit of overkill, but I'd rather use more memory than deal with a buffer overflow condition.


Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #46 on: June 12, 2019, 11:10:56 AM »
My eyes are going out on me. Now I see you allocated 4 MB buffer.

Hippy on the RPi forum used his Python / ScriptBasic extension module generator to create a GMP extension module. It still seg faults but his Python version is said to run.

RPi GMP

Can you see why I'm getting seg faults?

Offline AIR

  • BASIC Developer
  • Posts: 684
Re: fibonacci(4784969)
« Reply #47 on: June 12, 2019, 06:08:35 PM »
It looks like your code is not breaking out of the recursive nature of the function, and segfaults when the recursion limit is reached.
Have you tried a non-recursive approach instead?
The C version of this is slower than the GMP provided function; due to the recursive approach and the optimized math that GMP performs.
If all you're trying to do is return the sequence as a string, the function interface I provided does that.
If this is an exercise in coding more advanced stuff using libraries, then cool.  I would still suggest a non-recursive approach.

Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #48 on: June 12, 2019, 06:23:54 PM »
The bigintfibo is @hippy's code not mine. I'm just trying to get an extension built. Both Heatet and Hippy's code seg fault. Any chance you can whip up an ADD, SUB, MUL and DIV GMP extension module using SB strings?
« Last Edit: June 12, 2019, 06:28:20 PM by John »

Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #49 on: June 12, 2019, 08:34:44 PM »
Here is my attempt at a GMP extension module.

interface.c
Code: C
  1. /* GMP Extension Module
  2. UXLIBS: -lc -lgmp
  3. */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include <unistd.h>
  9. #include <gmp.h>
  10. #include "../../basext.h"
  11.  
  12.  
  13. /**************************
  14.  Extension Module Functions
  15. **************************/
  16.  
  17.  
  18. typedef struct _ModuleObject {
  19.   void *HandleArray;
  20. }ModuleObject,*pModuleObject;
  21.  
  22.  
  23. besVERSION_NEGOTIATE
  24.   return (int)INTERFACE_VERSION;
  25. besEND
  26.  
  27.  
  28. besSUB_START
  29.   pModuleObject p;
  30.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
  31.   if( besMODULEPOINTER == NULL )return 0;
  32.   p = (pModuleObject)besMODULEPOINTER;
  33.   return 0;
  34. besEND
  35.  
  36.  
  37. besSUB_FINISH
  38.   pModuleObject p;
  39.   p = (pModuleObject)besMODULEPOINTER;
  40.   if( p == NULL )return 0;
  41.   return 0;
  42. besEND
  43.  
  44.  
  45. /*************
  46.  GMP Functions
  47. *************/
  48.  
  49.  
  50. besFUNCTION(fibo)
  51.   int fval;
  52.  
  53.   besARGUMENTS("i")
  54.     &fval
  55.   besARGEND
  56.  
  57.   char buf[1500000];
  58.   memset(buf,0,1);
  59.   mpz_t res;
  60.   mpz_init(res);
  61.  
  62.   mpz_fib_ui(res, fval);
  63.  
  64.   gmp_snprintf( buf,sizeof(buf),"%Zd", res );
  65.  
  66.   besRETURN_STRING(buf);
  67.  
  68. besEND
  69.  
  70.  
  71. besFUNCTION(bi_add)
  72.   const char* s1;
  73.   const char* s2;
  74.  
  75.   besARGUMENTS("zz")
  76.     &s1, &s2
  77.   besARGEND
  78.  
  79.   char buf[1500000];
  80.   memset(buf,0,1);
  81.   mpz_t res;
  82.   mpz_init(res);
  83.  
  84.   mpz_add(res, s1, s2);
  85.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  86.  
  87.   besRETURN_STRING(buf);
  88.  
  89. besEND
  90.  
  91.  
  92. besFUNCTION(bi_sub)
  93.   const char* s1;
  94.   const char* s2;
  95.  
  96.   besARGUMENTS("zz")
  97.     &s1, &s2
  98.   besARGEND
  99.  
  100.   char buf[1500000];
  101.   memset(buf,0,1);
  102.   mpz_t res;
  103.   mpz_init(res);
  104.  
  105.   mpz_sub (res, s1, s2);
  106.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  107.  
  108.   besRETURN_STRING(buf);
  109.  
  110. besEND
  111.  
  112.  
  113. besFUNCTION(bi_mul)
  114.   const char* s1;
  115.   const char* s2;
  116.  
  117.   besARGUMENTS("zz")
  118.     &s1, &s2
  119.   besARGEND
  120.  
  121.   char buf[1500000];
  122.   memset(buf,0,1);
  123.   mpz_t res;
  124.   mpz_init(res);
  125.  
  126.   mpz_mul (res, s1, s2);
  127.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  128.  
  129.   besRETURN_STRING(buf);
  130.  
  131. besEND
  132.  

biadd.sb
Code: Script BASIC
  1. DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"
  2. DECLARE SUB BI_SUB    ALIAS  "bi_sub"  LIB "gmp"
  3. DECLARE SUB BI_MUL    ALIAS  "bi_mul"  LIB "gmp"
  4.  
  5.  
  6. a = "10000000000000001"
  7. b = "20000000000000002"
  8.  
  9. PRINT BI_ADD(a,b),"\n"
  10.  

Output

rs@jrs-laptop:~/sb/GMP$ scriba biadd.sb
GNU MP: Cannot reallocate memory (old_size=8 new_size=6467715464)
Aborted (core dumped)
jrs@jrs-laptop:~/sb/GMP$



Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #50 on: June 12, 2019, 09:18:18 PM »
At least I'm not getting a GMP error. Just a 0 for the result.  >:(

Code: C
  1. /* GMP Extension Module
  2. UXLIBS: -lc -lgmp
  3. */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include <unistd.h>
  9. #include <gmp.h>
  10. #include "../../basext.h"
  11.  
  12.  
  13. /**************************
  14.  Extension Module Functions
  15. **************************/
  16.  
  17.  
  18. typedef struct _ModuleObject {
  19.   void *HandleArray;
  20. }ModuleObject,*pModuleObject;
  21.  
  22.  
  23. besVERSION_NEGOTIATE
  24.   return (int)INTERFACE_VERSION;
  25. besEND
  26.  
  27.  
  28. besSUB_START
  29.   pModuleObject p;
  30.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
  31.   if( besMODULEPOINTER == NULL )return 0;
  32.   p = (pModuleObject)besMODULEPOINTER;
  33.   return 0;
  34. besEND
  35.  
  36.  
  37. besSUB_FINISH
  38.   pModuleObject p;
  39.   p = (pModuleObject)besMODULEPOINTER;
  40.   if( p == NULL )return 0;
  41.   return 0;
  42. besEND
  43.  
  44.  
  45. /*************
  46.  GMP Functions
  47. *************/
  48.  
  49.  
  50. besFUNCTION(fibo)
  51.   int fval;
  52.  
  53.   besARGUMENTS("i")
  54.     &fval
  55.   besARGEND
  56.  
  57.   char buf[1500000];
  58.   memset(buf,0,1);
  59.   mpz_t res;
  60.   mpz_init(res);
  61.  
  62.   mpz_fib_ui(res, fval);
  63.  
  64.   gmp_snprintf( buf,sizeof(buf),"%Zd", res );
  65.  
  66.   besRETURN_STRING(buf);
  67.  
  68. besEND
  69.  
  70.  
  71. besFUNCTION(bi_add)
  72.   const char* s1;
  73.   const char* s2;
  74.  
  75.   besARGUMENTS("zz")
  76.     &s1, &s2
  77.   besARGEND
  78.  
  79.   char buf[1500000];
  80.   memset(buf,0,1);
  81.   mpz_init(s1);
  82.   mpz_init(s2);
  83.   mpz_t res;
  84.   mpz_init(res);
  85.  
  86.   mpz_add(res, s1, s2);
  87.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  88.  
  89.   besRETURN_STRING(buf);
  90.  
  91. besEND
  92.  
  93.  
  94. besFUNCTION(bi_sub)
  95.   const char* s1;
  96.   const char* s2;
  97.  
  98.   besARGUMENTS("zz")
  99.     &s1, &s2
  100.   besARGEND
  101.  
  102.   char buf[1500000];
  103.   memset(buf,0,1);
  104.   mpz_init(s1);
  105.   mpz_init(s2);
  106.   mpz_t res;
  107.   mpz_init(res);
  108.  
  109.   mpz_sub (res, s1, s2);
  110.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  111.  
  112.   besRETURN_STRING(buf);
  113.  
  114. besEND
  115.  
  116.  
  117. besFUNCTION(bi_mul)
  118.   const char* s1;
  119.   const char* s2;
  120.  
  121.   besARGUMENTS("zz")
  122.     &s1, &s2
  123.   besARGEND
  124.  
  125.   char buf[1500000];
  126.   memset(buf,0,1);
  127.   mpz_init(s1);
  128.   mpz_init(s2);
  129.   mpz_t res;
  130.   mpz_init(res);
  131.  
  132.   mpz_mul (res, s1, s2);
  133.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  134.  
  135.   besRETURN_STRING(buf);
  136.  
  137. besEND
  138.  

Code: Script BASIC
  1. DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"
  2. DECLARE SUB BI_SUB    ALIAS  "bi_sub"  LIB "gmp"
  3. DECLARE SUB BI_MUL    ALIAS  "bi_mul"  LIB "gmp"
  4.  
  5. a = "10000000000000001"
  6. b = "20000000000000002"
  7.  
  8. PRINT BI_ADD(a,b),"\n"
  9.  


jrs@jrs-laptop:~/sb/GMP$ scriba biadd.sb
0
jrs@jrs-laptop:~/sb/GMP$


Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #51 on: June 12, 2019, 10:19:09 PM »
I got it to work. Testing at this time.

I can do a fibo(10000) in .5 seconds on my PoS laptop.

Code: Script BASIC
  1. DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"
  2. DECLARE SUB BI_SUB    ALIAS  "bi_sub"  LIB "gmp"
  3. DECLARE SUB BI_MUL    ALIAS  "bi_mul"  LIB "gmp"
  4.  
  5. FUNCTION sfibo (n)
  6.   IF n < 2 THEN
  7.     sfibo = 1
  8.   ELSE
  9.     m = 0
  10.     p = 1
  11.     q = 0
  12.     FOR i = 2 TO n
  13.       m = BI_ADD(p, q)
  14.       q = p
  15.       p = m
  16.     NEXT i
  17.     sfibo = m
  18.   END IF
  19. END FUNCTION
  20.  
  21. PRINT sfibo(10000),"\n"
  22.  
« Last Edit: June 12, 2019, 11:31:49 PM by John »

Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #52 on: June 13, 2019, 05:11:40 PM »
AIR,

I'm unable to do a million digit Fibonacci with this code. I run out of resources and the process is killed. Other than that it works great. Can you take a peek and see what might be causing the resource usage? I ran the fibo(87000) with the system monitor and I could see the memory ramping from 50% to 83% before the script finished and release the memory. I don't think I have a leak unless the 1.5 meg buffer I allocate each call isn't getting freed until the end.

I don't understand why I can't return the result of this function rather than having to create a 1.5 meg buffer and do a string copy.

Code: [Select]
char* res_string = mpz_get_str (0, BASE, res);
Code: C
  1. /* GMP Extension Module
  2. UXLIBS: -lc -lgmp
  3. */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include <unistd.h>
  9. #include <gmp.h>
  10. #include "../../basext.h"
  11.  
  12. static mpz_t op1;
  13. static mpz_t op2;
  14. static mpz_t res;
  15.  
  16. static void gmp_clear(void){
  17.   mpz_clear(op1);
  18.   mpz_clear(op2);
  19.   mpz_clear(res);
  20.   return 0;
  21. }
  22.  
  23. static void gmp_init(void){
  24.   mpz_init(op1);
  25.   mpz_init(op2);
  26.   mpz_init(res);
  27.   return 0;
  28. }
  29.  
  30.  
  31. /**************************
  32.  Extension Module Functions
  33. **************************/
  34.  
  35.  
  36. typedef struct _ModuleObject {
  37.   void *HandleArray;
  38. }ModuleObject,*pModuleObject;
  39.  
  40.  
  41. besVERSION_NEGOTIATE
  42.   return (int)INTERFACE_VERSION;
  43. besEND
  44.  
  45.  
  46. besSUB_START
  47.   pModuleObject p;
  48.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
  49.   if( besMODULEPOINTER == NULL )return 0;
  50.   p = (pModuleObject)besMODULEPOINTER;
  51.   return 0;
  52. besEND
  53.  
  54.  
  55. besSUB_FINISH
  56.   pModuleObject p;
  57.   p = (pModuleObject)besMODULEPOINTER;
  58.   if( p == NULL )return 0;
  59.   return 0;
  60. besEND
  61.  
  62.  
  63. /*************
  64.  GMP Functions
  65. *************/
  66.  
  67.  
  68. besFUNCTION(fibo)
  69.   int fval;
  70.  
  71.   besARGUMENTS("i")
  72.     &fval
  73.   besARGEND
  74.  
  75.   char buf[1500000];
  76.   memset(buf,0,1);
  77.   mpz_init(res);
  78.  
  79.   mpz_fib_ui(res, fval);
  80.  
  81.   gmp_snprintf( buf,sizeof(buf),"%Zd", res );
  82.   mpz_clear(res);
  83.  
  84.   besRETURN_STRING(buf);
  85.  
  86. besEND
  87.  
  88.  
  89. besFUNCTION(bi_add)
  90.   const char* s1;
  91.   const char* s2;
  92.  
  93.   besARGUMENTS("zz")
  94.     &s1, &s2
  95.   besARGEND
  96.  
  97.   char buf[1500000];
  98.   memset(buf,0,1);
  99.   gmp_init();
  100.   mpz_set_str(op1, s1, 10);
  101.   mpz_set_str(op2, s2, 10);
  102.  
  103.  
  104.   mpz_add(res, op1, op2);
  105.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  106.   gmp_clear();
  107.  
  108.   besRETURN_STRING(buf);
  109.  
  110. besEND
  111.  
  112.  
  113. besFUNCTION(bi_sub)
  114.   const char* s1;
  115.   const char* s2;
  116.  
  117.   besARGUMENTS("zz")
  118.     &s1, &s2
  119.   besARGEND
  120.  
  121.   char buf[1500000];
  122.   memset(buf,0,1);
  123.   gmp_init();
  124.   mpz_set_str(op1, s1, 10);
  125.   mpz_set_str(op2, s2, 10);
  126.  
  127.   mpz_sub (res, op1, op2);
  128.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  129.   gmp_clear();
  130.  
  131.   besRETURN_STRING(buf);
  132.  
  133. besEND
  134.  
  135.  
  136. besFUNCTION(bi_mul)
  137.   const char* s1;
  138.   const char* s2;
  139.  
  140.   besARGUMENTS("zz")
  141.     &s1, &s2
  142.   besARGEND
  143.  
  144.   char buf[1500000];
  145.   memset(buf,0,1);
  146.   gmp_init();
  147.   mpz_set_str(op1, s1, 10);
  148.   mpz_set_str(op2, s2, 10);
  149.  
  150.   mpz_mul (res, op1, op2);
  151.   gmp_snprintf(buf, sizeof(buf), "%Zd", res);
  152.   gmp_clear();
  153.  
  154.   besRETURN_STRING(buf);
  155.  
  156. besEND
  157.  

Code: Script BASIC
  1. DECLARE SUB BI_ADD    ALIAS  "bi_add"  LIB "gmp"
  2.  
  3. FUNCTION sfibo (n)
  4.   IF n < 2 THEN
  5.     sfibo = 1
  6.   ELSE
  7.     m = 0
  8.     p = 1
  9.     q = 0
  10.     FOR i = 2 TO n
  11.       m = BI_ADD(p, q)
  12.       q = p
  13.       p = m
  14.     NEXT i
  15.     sfibo = m
  16.   END IF
  17. END FUNCTION
  18.  
  19. PRINT LEN(sfibo(78000)),"\n"
  20.  
« Last Edit: June 13, 2019, 05:30:46 PM by John »

Offline AIR

  • BASIC Developer
  • Posts: 684
Re: fibonacci(4784969)
« Reply #53 on: June 13, 2019, 06:34:25 PM »
Code: C
  1. static void gmp_clear(void){
  2.   mpz_clear(op1);
  3.   mpz_clear(op2);
  4.   mpz_clear(res);
  5.   // return 0;  // you can't return a value from a void function (think SUB)
  6. }
  7.  
  8. static void gmp_init(void){
  9.   mpz_init(op1);
  10.   mpz_init(op2);
  11.   mpz_init(res);
  12. // return 0;  // you can't return a value from a void function (think SUB)
  13. }


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.   // char buf[1500000];
  10.   // memset(buf,0,1);
  11.   gmp_init();
  12.   mpz_set_str(op1, s1, 10);
  13.   mpz_set_str(op2, s2, 10);
  14.  
  15.  
  16.   mpz_add(res, op1, op2);
  17.   // gmp_snprintf(buf, sizeof(buf),
  18.   char* res_string = mpz_get_str (0, 10, res);
  19.   besSET_RETURN_STRING(res_string);
  20.   gmp_clear();
  21.   free(res_string);
  22.  
  23.   // besRETURN_STRING(buf);
  24.  
  25. besEND

AIR.

Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #54 on: June 13, 2019, 06:49:24 PM »
This is why they pay you the big bucks.

Thanks AIR!

I'll give this a try and take it as a learning experience.

Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #55 on: June 13, 2019, 08:33:31 PM »
Same result. I don't think this doubling method is the way to go. I read in the Python version comments that the recursive method only takes 59 recursions. I'm going to give that a try next.


jrs@jrs-laptop:~/sb/GMP$ time scriba sfibo.sb > sfibo.results
Killed

real   65m50.055s
user   3m49.076s
sys   0m12.994s
jrs@jrs-laptop:~/sb/GMP$


Code: C
  1. /* GMP Extension Module
  2. UXLIBS: -lc -lgmp
  3. */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include <unistd.h>
  9. #include <gmp.h>
  10. #include "../../basext.h"
  11.  
  12. static mpz_t op1;
  13. static mpz_t op2;
  14. static mpz_t res;
  15.  
  16. static void gmp_clear(void){
  17.   mpz_clear(op1);
  18.   mpz_clear(op2);
  19.   mpz_clear(res);
  20. }
  21.  
  22. static void gmp_init(void){
  23.   mpz_init(op1);
  24.   mpz_init(op2);
  25.   mpz_init(res);
  26. }
  27.  
  28.  
  29. /**************************
  30.  Extension Module Functions
  31. **************************/
  32.  
  33.  
  34. typedef struct _ModuleObject {
  35.   void *HandleArray;
  36. }ModuleObject,*pModuleObject;
  37.  
  38.  
  39. besVERSION_NEGOTIATE
  40.   return (int)INTERFACE_VERSION;
  41. besEND
  42.  
  43.  
  44. besSUB_START
  45.   pModuleObject p;
  46.   besMODULEPOINTER = besALLOC(sizeof(ModuleObject));
  47.   if( besMODULEPOINTER == NULL )return 0;
  48.   p = (pModuleObject)besMODULEPOINTER;
  49.   return 0;
  50. besEND
  51.  
  52.  
  53. besSUB_FINISH
  54.   pModuleObject p;
  55.   p = (pModuleObject)besMODULEPOINTER;
  56.   if( p == NULL )return 0;
  57.   return 0;
  58. besEND
  59.  
  60.  
  61. /*************
  62.  GMP Functions
  63. *************/
  64.  
  65.  
  66. besFUNCTION(fibo)
  67.   int fval;
  68.  
  69.   besARGUMENTS("i")
  70.     &fval
  71.   besARGEND
  72.  
  73.   char buf[1500000];
  74.   memset(buf,0,1);
  75.   mpz_init(res);
  76.  
  77.   mpz_fib_ui(res, fval);
  78.  
  79.   gmp_snprintf( buf,sizeof(buf),"%Zd", res );
  80.   mpz_clear(res);
  81.  
  82.   besRETURN_STRING(buf);
  83.  
  84. besEND
  85.  
  86.  
  87. besFUNCTION(bi_add)
  88.   const char* s1;
  89.   const char* s2;
  90.  
  91.   besARGUMENTS("zz")
  92.     &s1, &s2
  93.   besARGEND
  94.  
  95.   gmp_init();
  96.   mpz_set_str(op1, s1, 10);
  97.   mpz_set_str(op2, s2, 10);
  98.  
  99.   mpz_add(res, op1, op2);
  100.   char* res_string = mpz_get_str (0, 10, res);
  101.   besSET_RETURN_STRING(res_string);
  102.   gmp_clear();
  103.   free(res_string);
  104.  
  105. besEND
  106.  
  107.  
  108. besFUNCTION(bi_sub)
  109.   const char* s1;
  110.   const char* s2;
  111.  
  112.   besARGUMENTS("zz")
  113.     &s1, &s2
  114.   besARGEND
  115.  
  116.   gmp_init();
  117.   mpz_set_str(op1, s1, 10);
  118.   mpz_set_str(op2, s2, 10);
  119.  
  120.   mpz_sub (res, op1, op2);
  121.   char* res_string = mpz_get_str (0, 10, res);
  122.   besSET_RETURN_STRING(res_string);
  123.   gmp_clear();
  124.   free(res_string);
  125.  
  126. besEND
  127.  
  128.  
  129. besFUNCTION(bi_mul)
  130.   const char* s1;
  131.   const char* s2;
  132.  
  133.   besARGUMENTS("zz")
  134.     &s1, &s2
  135.   besARGEND
  136.  
  137.   gmp_init();
  138.   mpz_set_str(op1, s1, 10);
  139.   mpz_set_str(op2, s2, 10);
  140.  
  141.   mpz_mul (res, op1, op2);
  142.   char* res_string = mpz_get_str (0, 10, res);
  143.   besSET_RETURN_STRING(res_string);
  144.   gmp_clear();
  145.   free(res_string);
  146.  
  147. besEND
  148.  

Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #56 on: June 14, 2019, 12:29:42 PM »
AIR,

I'm having no luck trying to convert the Python and JavaScript Fibo examples to SB I have been given. I feel the GMP extension module is solid and just needs a Fibo routine that take advantage of the design using SB strings as temp BINGINT storage.

Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #57 on: June 14, 2019, 06:36:55 PM »
I tried their recursive fibo submissions and they were extremely SLOW!

I can do the Fibonacci 500 in .017 seconds. That includes printing all 500 fibos.

RPi Forum Post
« Last Edit: June 14, 2019, 06:42:55 PM by John »

Offline AIR

  • BASIC Developer
  • Posts: 684
Re: fibonacci(4784969)
« Reply #58 on: June 14, 2019, 07:43:37 PM »
Screw all that bullshit, do it in the module.  That's what they're for, to provide performance when an interpreted approach is too slow.  Even Python does this, so why limit yourself when the Module system can get you the performance you want?


Original code attribution: https://codegolf.stackexchange.com/a/9444 by Erik Haliewicz.
Code: C
  1. besFUNCTION(fib2)
  2.   int fval, count;
  3.   mpz_t a, b, p, q, psq, qsq, twopq, bq, aq, ap, bp;
  4.  
  5.   besARGUMENTS("i")
  6.     &fval
  7.   besARGEND
  8.  
  9.   count = fval;
  10.  
  11.   mpz_init_set_si(a, 1);
  12.   mpz_init_set_si(b, 0);
  13.   mpz_init_set_si(p, 0);
  14.   mpz_init_set_si(q, 1);
  15.   mpz_init(psq);
  16.   mpz_init(qsq);
  17.   mpz_init(twopq);
  18.   mpz_init(bq);
  19.   mpz_init(aq);
  20.   mpz_init(ap);
  21.   mpz_init(bp);
  22.  
  23.  while(count > 0) {
  24.   if ((count % 2) == 0) {
  25.     mpz_mul(psq, p, p);
  26.     mpz_mul(qsq, q, q);
  27.     mpz_mul(twopq, p, q);
  28.     mpz_mul_si(twopq, twopq, 2);
  29.  
  30.     mpz_add(p, psq, qsq);
  31.     mpz_add(q, twopq, qsq);
  32.     count/=2;
  33.   }else{
  34.     mpz_mul(bq, b, q);
  35.     mpz_mul(aq, a, q);
  36.     mpz_mul(ap, a, p);
  37.     mpz_mul(bp, b, p);
  38.  
  39.     mpz_add(a, bq, aq);
  40.     mpz_add(a, a, ap);
  41.  
  42.     mpz_add(b, bp, aq);
  43.  
  44.     count--;
  45.     }
  46.  
  47. }
  48.  
  49. char* res_string = mpz_get_str (0, 10, b);
  50. besSET_RETURN_STRING(res_string);
  51. free(res_string);
  52.  
  53.  
  54. besEND


On my Mac Mini, the above takes about a 1.5 seconds, INCLUDING printing.  4784969.

AIR.

« Last Edit: June 14, 2019, 08:15:49 PM by AIR »

Offline John

  • Forum Support / SB Dev
  • Posts: 2745
    • ScriptBasic Open Source Project
Re: fibonacci(4784969)
« Reply #59 on: June 15, 2019, 10:58:03 AM »
Thanks AIR!

I will update the fibo function in the GMP extension module.

I was able to do the 1 mil challenge with Heater recursive fib code. Completes in minute using GMP.

Thanks for all your help with this. Without you this wouldn't have been possible.