Code: Select all

```
if n <= 2 then
hfibo = 1
```

I'm not sure why there is even an "r" in there. Why not just set hfibo? Isn't that the return value?
Is still wrong for n = 0.

Code: Select all

```
if n <= 2 then
hfibo = 1
```

Memory in C++ is a leaky abstraction .

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

That fixed it. Now I have to see if I can add the the GMP functions to extend integer math.

Code: Select all

```
function hfibo(n)
local a, b, fk, fk1, k, r
split "0,0,0,0,0,0" by "," to k, a, b, r, fk, fk1
if n <= 2 then
r = 1
else
k = n \ 2
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n and 1 = 0 then
a = fk1 + fk1
b = a - fk
r = fk * b
else
a = fk * fk
b = fk1 * fk1
r = a + b
end if
end if
hfibo = r
end function
print format("%.f\n",hfibo(78))
```

Code: Select all

```
jrs@jrs-laptop:~/sb/GMP$ time scriba nfibo.sb
28174687879107533504249856
real 0m0.011s
user 0m0.007s
sys 0m0.004s
jrs@jrs-laptop:~/sb/GMP$
```

ScriptBasic,

Yay!That fixed it....

This is a tense moment...Now I have to see if I can add the the GMP functions to extend integer math.

Memory in C++ is a leaky abstraction .

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

It's not returning the correct results for **fibo(78)**

Your code.

Code: Select all

```
DECLARE SUB BI_ADD ALIAS "bi_add" LIB "gmp"
FUNCTION sfibo (n)
IF n < 2 THEN
sfibo = 1
ELSE
m = 0
p = 1
q = 0
FOR i = 2 TO n
m = p + q
' m = BI_ADD(p, q)
q = p
p = m
NEXT i
sfibo = m
END IF
END FUNCTION
PRINT FORMAT("%.f\n",sfibo(78))
jrs@jrs-laptop:~/sb/GMP$ time scriba sbfibo
8944394323791464
real 0m0.007s
user 0m0.006s
sys 0m0.001s
jrs@jrs-laptop:~/sb/GMP$
```

Code: Select all

```
jrs@jrs-laptop:~/sb/GMP$ time scriba nfibo.sb
28174687879107533504249856
real 0m0.011s
user 0m0.007s
sys 0m0.004s
jrs@jrs-laptop:~/sb/GMP$
```

Do you think the FORMAT in the print is necessary?ScriptBasic wrote: ↑Sat Jun 15, 2019 5:36 amIt's not returning the correct results forfibo(78)

Your code.Code: Select all

`DECLARE SUB BI_ADD ALIAS "bi_add" LIB "gmp" FUNCTION sfibo (n) IF n < 2 THEN sfibo = 1 ELSE m = 0 p = 1 q = 0 FOR i = 2 TO n m = p + q ' m = BI_ADD(p, q) q = p p = m NEXT i sfibo = m END IF END FUNCTION PRINT FORMAT("%.f\n",sfibo(78)) jrs@jrs-laptop:~/sb/GMP$ time scriba sbfibo 8944394323791464 real 0m0.007s user 0m0.006s sys 0m0.001s jrs@jrs-laptop:~/sb/GMP$`

Code: Select all

`jrs@jrs-laptop:~/sb/GMP$ time scriba nfibo.sb 28174687879107533504249856 real 0m0.011s user 0m0.007s sys 0m0.004s jrs@jrs-laptop:~/sb/GMP$`

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

You're right, it's not needed.Do you think the FORMAT in the print is necessary?

Code: Select all

```
jrs@jrs-laptop:~/sb/GMP$ time scriba sbfibo
8944394323791464
real 0m0.007s
user 0m0.003s
sys 0m0.004s
jrs@jrs-laptop:~/sb/GMP$
```

Code: Select all

```
jrs@jrs-laptop:~/sb/GMP$ time scriba nfibo.sb
2.817469e+25
real 0m0.010s
user 0m0.007s
sys 0m0.003s
jrs@jrs-laptop:~/sb/GMP$
```

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

I have good news and bad news, The bad news is Heater's code isn't returning the correct answer., The good news is the code now works with the GMP library and is faster than the native GMP fibo function.

**hfibo.sb**
GMP native **fibo()** function

If you can fix the results, this may be a contender.

Code: Select all

```
DECLARE SUB BI_ADD ALIAS "bi_add" LIB "gmp"
DECLARE SUB BI_SUB ALIAS "bi_sub" LIB "gmp"
DECLARE SUB BI_MUL ALIAS "bi_mul" LIB "gmp"
function hfibo(n)
local a, b, fk, fk1, k, r
SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1
if n <= 2 THEN
r = 1
else
k = n \ 2
fk = hfibo(k)
fk1 = hfibo(BI_ADD(k, 1))
if n and 2 = 0 then
a = BI_ADD(fk1, fk1)
b = BI_SUB(a, fk)
r = BI_MUL(fk, b)
else
a = BI_MUL(fk, fk)
b = BI_MUL(fk1, fk1)
r = BI_ADD(a, b)
end if
end if
hfibo = r
end function
PRINT hfibo(1000),"\n"
jrs@jrs-laptop:~/sb/GMP$ time scriba hfibo.sb
20350335938545493080033473043096993561063758224896175591371555186482072913954184091750603015959482920845011335150909087228815317158088017664736868103572712040512042684519983963892676140488116417020896237917333067264556783476175530767550000008
real 0m0.019s
user 0m0.019s
sys 0m0.000s
jrs@jrs-laptop:~/sb/GMP$
```

Code: Select all

```
DECLARE SUB fibo ALIAS "fibo" LIB "gmp"
PRINT fibo(1000),"\n"
jrs@jrs-laptop:~/sb/GMP$ time scriba fibo.sb
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
real 0m0.031s
user 0m0.001s
sys 0m0.005s
jrs@jrs-laptop:~/sb/GMP$
```

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

Since JavaScript has become so popular, maybe Peter screwed up an should have called it

Be thankful I wasn't the one to name the language. I would have called it

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

Original code attribution: https://codegolf.stackexchange.com/a/9444 by Erik Haliewicz.Code: Select all

`besFUNCTION(fib2) int fval, count; mpz_t a, b, p, q, psq, qsq, twopq, bq, aq, ap, bp; besARGUMENTS("i") &fval besARGEND count = fval; mpz_init_set_si(a, 1); mpz_init_set_si(b, 0); mpz_init_set_si(p, 0); mpz_init_set_si(q, 1); mpz_init(psq); mpz_init(qsq); mpz_init(twopq); mpz_init(bq); mpz_init(aq); mpz_init(ap); mpz_init(bp); while(count > 0) { if ((count % 2) == 0) { mpz_mul(psq, p, p); mpz_mul(qsq, q, q); mpz_mul(twopq, p, q); mpz_mul_si(twopq, twopq, 2); mpz_add(p, psq, qsq); mpz_add(q, twopq, qsq); count/=2; }else{ mpz_mul(bq, b, q); mpz_mul(aq, a, q); mpz_mul(ap, a, p); mpz_mul(bp, b, p); mpz_add(a, bq, aq); mpz_add(a, a, ap); mpz_add(b, bp, aq); count--; } } char* res_string = mpz_get_str (0, 10, b); besSET_RETURN_STRING(res_string); free(res_string); besEND`

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

AIR.

Last edited by John_Spikowski on Sat Jun 15, 2019 9:41 am, edited 1 time in total.

ScriptBasic,

Could you please stop referring to your code as "Heater's code"

Heater's code works correctly, at least as posted here:

viewtopic.php?f=31&t=240287&start=425#p1480565

Heater has many other working fibo codes in here: https://github.com/ZiCog/fibo_4784969 (Not all by me of course)

I may have suggested the algorithm and shown examples, in two languages, but it's your code that not working.

Now, let's see what we can do about it:

1) Can you fix the base cases so that it returns the correct results for n = 0, 1, and 2. As suggested once or twice above already. Returning a 1 for fibo(0) will get you the wrong results.

2) Can you change:

fk1 = hfibo(BI_ADD(k, 1))

to:

fk1 = hfibo(k, 1)

this function does not need a big integer parameter.

Could you please stop referring to your code as "Heater's code"

Heater's code works correctly, at least as posted here:

viewtopic.php?f=31&t=240287&start=425#p1480565

Heater has many other working fibo codes in here: https://github.com/ZiCog/fibo_4784969 (Not all by me of course)

I may have suggested the algorithm and shown examples, in two languages, but it's your code that not working.

Now, let's see what we can do about it:

1) Can you fix the base cases so that it returns the correct results for n = 0, 1, and 2. As suggested once or twice above already. Returning a 1 for fibo(0) will get you the wrong results.

2) Can you change:

fk1 = hfibo(BI_ADD(k, 1))

to:

fk1 = hfibo(k, 1)

this function does not need a big integer parameter.

Memory in C++ is a leaky abstraction .

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

I'm not sure what you mean. Can you post the corrected ScriptBasic code?1) Can you fix the base cases so that it returns the correct results for n = 0, 1, and 2. As suggested once or twice above already. Returning a 1 for fibo(0) will get you the wrong results.

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

Code: Select all

```
jrs@jrs-laptop:~/sb/GMP$ time scriba hfibo.sb
265858423089533551045805128410440667760792042653165038872597794041604264634214336337052045724438921594488629846599524054315535532547586868663440236180213246915192649900774666306374132896317696001059682229718989734400256874921907275384042888739727596805000
real 0m0.026s
user 0m0.017s
sys 0m0.009s
jrs@jrs-laptop:~/sb/GMP$
```

Code: Select all

```
DECLARE SUB BI_ADD ALIAS "bi_add" LIB "gmp"
DECLARE SUB BI_SUB ALIAS "bi_sub" LIB "gmp"
DECLARE SUB BI_MUL ALIAS "bi_mul" LIB "gmp"
function hfibo(n)
local a, b, fk, fk1, k, r
SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1
if n <= 2 THEN
r = 1
else
k = n \ 2
fk = hfibo(k)
fk1 = hfibo(k + 1)
if n and 2 = 0 then
a = BI_ADD(fk1, fk1)
b = BI_SUB(a, fk)
r = BI_MUL(fk, b)
else
a = BI_MUL(fk, fk)
b = BI_MUL(fk1, fk1)
r = BI_ADD(a, b)
end if
end if
hfibo = r
end function
PRINT hfibo(1000),"\n"
```

fibo(1) = 1

fibo(2) = 1

fibo(3) = 2

ScriptBasic,

fib(0) returns 0

fib(1) returns 1

fib(2) returns 1

I have shown how to do this in two different ways in the Javascript and Python hfibos here:

viewtopic.php?f=31&t=240287&start=425#p1480579

I mean that this should happen:I'm not sure what you mean.

fib(0) returns 0

fib(1) returns 1

fib(2) returns 1

I don't speak ScriptBasic so I don't like to post any ScriptBasic code, it would likely be wrong.Can you post the corrected ScriptBasic code?

I have shown how to do this in two different ways in the Javascript and Python hfibos here:

viewtopic.php?f=31&t=240287&start=425#p1480579

Memory in C++ is a leaky abstraction .

ScriptBasic,

This line is wrong:

if n and 2 = 0 then

Should be:

if n and 1 = 0 then

What is the operator operator precedence in ScriptBasic? Does it really do the "and" first?

I would prefer to see:

if (n and 1) = 0 then

Actually I can see by the result you are getting that that "if expression" also failing. I can get the same result as you by breaking my python hfibo in the same way!

This line is wrong:

if n and 2 = 0 then

Should be:

if n and 1 = 0 then

What is the operator operator precedence in ScriptBasic? Does it really do the "and" first?

I would prefer to see:

if (n and 1) = 0 then

Actually I can see by the result you are getting that that "if expression" also failing. I can get the same result as you by breaking my python hfibo in the same way!

Memory in C++ is a leaky abstraction .

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

Works now.

Was:

if (n and 2) = 0 then

Changed:

if (n and 1) = 0 then

**Output and GMP Fibo(1000) compare**

Was:

if (n and 2) = 0 then

Changed:

if (n and 1) = 0 then

Code: Select all

```
DECLARE SUB BI_ADD ALIAS "bi_add" LIB "gmp"
DECLARE SUB BI_SUB ALIAS "bi_sub" LIB "gmp"
DECLARE SUB BI_MUL ALIAS "bi_mul" LIB "gmp"
function hfibo(n)
local a, b, fk, fk1, k, r
SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1
if n <= 2 THEN
r = 1
else
k = (n / 2) OR 0
fk = hfibo(k)
fk1 = hfibo(k + 1)
if (n and 1) = 0 then
a = BI_ADD(fk1, fk1)
b = BI_SUB(a, fk)
r = BI_MUL(fk, b)
else
a = BI_MUL(fk, fk)
b = BI_MUL(fk1, fk1)
r = BI_ADD(a, b)
end if
end if
hfibo = r
end function
PRINT hfibo(1000),"\n"
```

Code: Select all

```
jrs@jrs-laptop:~/sb/GMP$ scriba hfibo.sb
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
jrs@jrs-laptop:~/sb/GMP$ scriba fibo.sb
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
jrs@jrs-laptop:~/sb/GMP$
```

Yay! Excellent!

Time to go for the big one: fibo(4784969)

Time to go for the big one: fibo(4784969)

Memory in C++ is a leaky abstraction .

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

Code: Select all

```
jrs@jrs-laptop:~/sb/GMP$ time scriba hfibo.sb > 1milfibo
real 1m9.272s
user 1m8.457s
sys 0m0.784s
jrs@jrs-laptop:~/sb/GMP$ ls -l 1milfibo
-rw-r--r-- 1 jrs jrs 1000001 Jun 15 01:45 1milfibo
jrs@jrs-laptop:~/sb/GMP$ tail -c64 1milfibo
330930391815964864885353407167474856539211500699706378405156269
jrs@jrs-laptop:~/sb/GMP$
```

ScriptBasic,

Well done.

If you can get that included in the out of the box installation of ScriptBasic I'll check it out. There is a place in the Fibo 4784969 Hall of Fame awaiting.

Well done.

If you can get that included in the out of the box installation of ScriptBasic I'll check it out. There is a place in the Fibo 4784969 Hall of Fame awaiting.

Memory in C++ is a leaky abstraction .

- John_Spikowski
**Posts:**1614**Joined:**Wed Apr 03, 2019 5:53 pm**Location:**Anacortes, WA USA-
**Contact:**Website Twitter

Thanks.

I want to get BI_DIV and BI_IDIV added to the library before adding it to default modules for the distro.

I want to get BI_DIV and BI_IDIV added to the library before adding it to default modules for the distro.

It would wouldn't it. You are setting hfibo = r just before returning every time, and when n <= 2 it never sets r.ScriptBasic wrote: ↑Sat Jun 15, 2019 3:42 amThis still returns zero for me.

Code: Select all

`function hfibo(n) local a, b, fk, fk1, k, r split "0,0,0,0,0,0" by "," to k, a, b, r, fk, fk1 if n <= 2 then hfibo = 1 else ... end if hfibo = r end function`

That bug is in my version too; and hence I presume that "Mandatory parameter missing" error because I never initialised 'r'. Though I'm getting a segmentation fault as expected with that and other fixes, variables made local.

Looks like everything works.

Except fibo(0) will come out as 1 instead of 0 with the last code ScripBasic posted.

Except fibo(0) will come out as 1 instead of 0 with the last code ScripBasic posted.

Memory in C++ is a leaky abstraction .

That can easily be fixed with

Code: Select all

```
REM The function hfibo(n) returns the nth
REM Fibonacci number for n = 1, 2, 3, ...
```

It's also worth remembering that none of our fibo programs (except maybe fibo_phi.py) compute or approximate F(n) for non-integer values such as n=2.5 and most don't work when n is negative.

One could.

Except one generally finds the Fibonacci sequence defined such that each number is the sum of the two preceding ones, starting from 0 and 1.

For example: https://oeis.org/search?q=fibonacci&lan ... &go=Search

All that talk of negative fibo and non-integer fibo is stuff and nonsense

Besides, it's quicker to fix the code than write the comment excusing the bug!

Except one generally finds the Fibonacci sequence defined such that each number is the sum of the two preceding ones, starting from 0 and 1.

For example: https://oeis.org/search?q=fibonacci&lan ... &go=Search

All that talk of negative fibo and non-integer fibo is stuff and nonsense

Besides, it's quicker to fix the code than write the comment excusing the bug!

Memory in C++ is a leaky abstraction .

Ah, but the comment has already been written.Heater wrote: ↑Sat Jun 15, 2019 3:58 pmOne could.

Except one generally finds the Fibonacci sequence defined such that each number is the sum of the two preceding ones, starting from 0 and 1.

For example: https://oeis.org/search?q=fibonacci&lan ... &go=Search

All that talk of negative fibo and non-integer fibo is stuff and nonsense

Besides, it's quicker to fix the code than write the comment excusing the bug!

The Fibonacci sequence was originally developed as a model for the growth of rabbit populations.

More information available here states

While real-world experience may suggest otherwise, mathematically, if your breeding experiment starts with zero pairs of rabbits, then no baby rabbits will ever be produced.Suppose a newly-born pair of rabbits, one male, one female, are put in a field. Rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits. Suppose that our rabbits never die and that the female always produces one new pair (one male, one female) every month from the second month on. The puzzle that Fibonacci posed was...

How many pairs will there be in one year?

ejolson,

At time zero there are zero rabbits in the field. Ergo fibo(0) == 0.

But, but, the resolution of that apparent paradox is in the very description of the rabbit breading experiment you quoted above.While real-world experience may suggest otherwise, mathematically, if your breeding experiment starts with zero pairs of rabbits, then no baby rabbits will ever be produced.

It's unstated but I think we are supposed to assume there are no rabbits in the field before we but those baby rabbits there."Suppose a newly-born pair of rabbits, one male, one female, are put in a field."

At time zero there are zero rabbits in the field. Ergo fibo(0) == 0.

Memory in C++ is a leaky abstraction .