## Liberation through Computer Literacy

Heater
Posts: 14287
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

I'm not sure why there is even an "r" in there. Why not just set hfibo? Isn't that the return value?

Code: Select all

``````if n <= 2 then
hfibo = 1
``````
Is still wrong for n = 0.
Memory in C++ is a leaky abstraction .

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

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\$
``````

Heater
Posts: 14287
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

ScriptBasic,
That fixed it....
Yay!
Now I have to see if I can add the the GMP functions to extend integer math.
This is a tense moment...
Memory in C++ is a leaky abstraction .

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

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

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
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\$
``````

ejolson
Posts: 4077
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

ScriptBasic wrote:
Sat Jun 15, 2019 5:36 am
It's not returning the correct results for fibo(78)

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
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?

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

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

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\$
``````
This is what you get with Heater's code if you don't use format.

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

### Re: A Final Fibonacci Challenge

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

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)
if n and 2 = 0 then
b = BI_SUB(a, fk)
r = BI_MUL(fk, b)
else
a = BI_MUL(fk, fk)
b = BI_MUL(fk1, fk1)
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\$
``````
GMP native fibo() function

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\$
``````
If you can fix the results, this may be a contender.

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

OT

Since JavaScript has become so popular, maybe Peter screwed up an should have called it BasicScript. We will never know.

Be thankful I wasn't the one to name the language. I would have called it SOB. (Snap On Basic)

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

Fibo2

AIR created a new fibo function for the GMP extension module.
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);

count/=2;
}else{
mpz_mul(bq, b, q);
mpz_mul(aq, a, q);
mpz_mul(ap, a, p);
mpz_mul(bp, b, p);

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.

Heater
Posts: 14287
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

ScriptBasic,

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:

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

### Re: A Final Fibonacci Challenge

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.
I'm not sure what you mean. Can you post the corrected ScriptBasic code?

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

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\$
``````
The result is still wrong after the change requested, It did change though.

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
b = BI_SUB(a, fk)
r = BI_MUL(fk, b)
else
a = BI_MUL(fk, fk)
b = BI_MUL(fk1, fk1)
end if
end if
hfibo = r
end function

PRINT hfibo(1000),"\n"
``````
fibo(0) = 1
fibo(1) = 1
fibo(2) = 1
fibo(3) = 2

Heater
Posts: 14287
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

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

fib(0) returns 0
fib(1) returns 1
fib(2) returns 1
Can you post the corrected ScriptBasic code?
I don't speak ScriptBasic so I don't like to post any ScriptBasic code, it would likely be wrong.

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 .

Heater
Posts: 14287
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

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!
Memory in C++ is a leaky abstraction .

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

Works now.

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
b = BI_SUB(a, fk)
r = BI_MUL(fk, b)
else
a = BI_MUL(fk, fk)
b = BI_MUL(fk1, fk1)
end if
end if
hfibo = r
end function

PRINT hfibo(1000),"\n"
``````
Output and GMP Fibo(1000) compare

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\$
``````

Heater
Posts: 14287
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

Yay! Excellent!

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

### Re: A Final Fibonacci Challenge

Heater wrote:
Sat Jun 15, 2019 8:45 am
Yay! Excellent!

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

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\$
``````
I would like to thank Heater, AIR and ejolson for their assistance making this a reality.

Heater
Posts: 14287
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

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.
Memory in C++ is a leaky abstraction .

John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

Thanks.

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

hippy
Posts: 6544
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

### Re: A Final Fibonacci Challenge

ScriptBasic wrote:
Sat Jun 15, 2019 3:42 am
This 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
``````
It would wouldn't it. You are setting hfibo = r just before returning every time, and when n <= 2 it never sets r.

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.

Heater
Posts: 14287
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

Looks like everything works.

Except fibo(0) will come out as 1 instead of 0 with the last code ScripBasic posted.
Memory in C++ is a leaky abstraction .

ejolson
Posts: 4077
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

Heater wrote:
Sat Jun 15, 2019 12:16 pm
Looks like everything works.

Except fibo(0) will come out as 1 instead of 0 with the last code ScripBasic posted.
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, ...``````
Note that fibench uses n=0 to mean stop computing and exit.

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.

Heater
Posts: 14287
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

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!
Memory in C++ is a leaky abstraction .

ejolson
Posts: 4077
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

Heater wrote:
Sat Jun 15, 2019 3:58 pm
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!
Ah, but the comment has already been written.

The Fibonacci sequence was originally developed as a model for the growth of rabbit populations. 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?
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.

Heater
Posts: 14287
Joined: Tue Jul 17, 2012 3:02 pm

### Re: A Final Fibonacci Challenge

ejolson,
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.
But, but, the resolution of that apparent paradox is in the very description of the rabbit breading experiment you quoted above.
"Suppose a newly-born pair of rabbits, one male, one female, are put in a field."
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.

At time zero there are zero rabbits in the field. Ergo fibo(0) == 0.
Memory in C++ is a leaky abstraction .