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

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 5:14 am

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.

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 5:17 am

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

[email protected]:~/sb/GMP$ time scriba nfibo.sb
28174687879107533504249856

real	0m0.011s
user	0m0.007s
sys	0m0.004s
[email protected]:~/sb/GMP$ 

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

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 5:20 am

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

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

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
'     m = BI_ADD(p, q)
      q = p
      p = m
    NEXT i
    sfibo = m
  END IF
END FUNCTION

PRINT FORMAT("%.f\n",sfibo(78))


[email protected]:~/sb/GMP$ time scriba sbfibo
8944394323791464

real	0m0.007s
user	0m0.006s
sys	0m0.001s
[email protected]:~/sb/GMP$ 
Your code.

Code: Select all

[email protected]:~/sb/GMP$ time scriba nfibo.sb
28174687879107533504249856

real	0m0.011s
user	0m0.007s
sys	0m0.004s
[email protected]:~/sb/GMP$ 

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

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 5:40 am

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
'     m = BI_ADD(p, q)
      q = p
      p = m
    NEXT i
    sfibo = m
  END IF
END FUNCTION

PRINT FORMAT("%.f\n",sfibo(78))


[email protected]:~/sb/GMP$ time scriba sbfibo
8944394323791464

real	0m0.007s
user	0m0.006s
sys	0m0.001s
[email protected]:~/sb/GMP$ 
Your code.

Code: Select all

[email protected]:~/sb/GMP$ time scriba nfibo.sb
28174687879107533504249856

real	0m0.011s
user	0m0.007s
sys	0m0.004s
[email protected]:~/sb/GMP$ 
Do you think the FORMAT in the print is necessary?

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 5:47 am

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

Code: Select all

[email protected]:~/sb/GMP$ time scriba sbfibo
8944394323791464

real	0m0.007s
user	0m0.003s
sys	0m0.004s
[email protected]:~/sb/GMP$ 
This is what you get with Heater's code if you don't use format.

Code: Select all

[email protected]:~/sb/GMP$ time scriba nfibo.sb
2.817469e+25
real	0m0.010s
user	0m0.007s
sys	0m0.003s
[email protected]:~/sb/GMP$ 

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 6:26 am

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)
    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"


[email protected]:~/sb/GMP$ time scriba hfibo.sb
20350335938545493080033473043096993561063758224896175591371555186482072913954184091750603015959482920845011335150909087228815317158088017664736868103572712040512042684519983963892676140488116417020896237917333067264556783476175530767550000008

real	0m0.019s
user	0m0.019s
sys	0m0.000s
[email protected]:~/sb/GMP$
GMP native fibo() function

Code: Select all

DECLARE SUB fibo ALIAS "fibo" LIB "gmp"

PRINT fibo(1000),"\n"

[email protected]:~/sb/GMP$ time scriba fibo.sb
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

real	0m0.031s
user	0m0.001s
sys	0m0.005s
[email protected]:~/sb/GMP$ 
If you can fix the results, this may be a contender.

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 7:15 am

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)

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 7:59 am

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);

    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 ScriptBasic on Sat Jun 15, 2019 9:41 am, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 8:01 am

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.

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 8:05 am

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?

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 8:09 am

Code: Select all

[email protected]:~/sb/GMP$ time scriba hfibo.sb
265858423089533551045805128410440667760792042653165038872597794041604264634214336337052045724438921594488629846599524054315535532547586868663440236180213246915192649900774666306374132896317696001059682229718989734400256874921907275384042888739727596805000

real	0m0.026s
user	0m0.017s
sys	0m0.009s
[email protected]:~/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
      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(0) = 1
fibo(1) = 1
fibo(2) = 1
fibo(3) = 2

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

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 8:22 am

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

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

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 8:28 am

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!

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 8:39 am

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
      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"
Output and GMP Fibo(1000) compare

Code: Select all

[email protected]:~/sb/GMP$ scriba hfibo.sb
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
[email protected]:~/sb/GMP$ scriba fibo.sb
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
[email protected]:~/sb/GMP$ 

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

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 8:45 am

Yay! Excellent!

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

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 8:50 am

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

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

Code: Select all

[email protected]:~/sb/GMP$ time scriba hfibo.sb > 1milfibo

real	1m9.272s
user	1m8.457s
sys	0m0.784s
[email protected]:~/sb/GMP$ ls -l 1milfibo
-rw-r--r-- 1 jrs jrs 1000001 Jun 15 01:45 1milfibo
[email protected]:~/sb/GMP$ tail -c64 1milfibo
330930391815964864885353407167474856539211500699706378405156269
[email protected]:~/sb/GMP$ 
I would like to thank Heater, AIR and ejolson for their assistance making this a reality.

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

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 9:03 am

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.

User avatar
ScriptBasic
Posts: 1254
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 9:16 am

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: 5371
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 11:41 am

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: 12722
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

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.

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

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 3:12 pm

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: 12722
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

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!

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

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 4:22 pm

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.

Image

More information available here states
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: 12722
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Sat Jun 15, 2019 6:25 pm

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.

Return to “General programming discussion”