fibonacci(4784969)

[AIR]

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.

[John]

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?

[AIR]

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.

[John]

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?

[John]

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: ScriptBasic

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$

[John]

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: ScriptBasic

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$

[John]

I got it to work. Testing at this time.

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

Code: ScriptBasic

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.  

[John]

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: ScriptBasic

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.  

[AIR]

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.

[John]

This is why they pay you the big bucks.

Thanks AIR!

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

[John]

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.  

[John]

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.

[John]

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

[AIR]

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.

[John]

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.