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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 8:44 am

This seg faults for me. Maybe you can see what I'm doing wrong since it's your code. Probably doesn't like the undef's being passed to 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 fiboNoMemo(n)
  if n <= 1 THEN
    fiboNoMemo = n
  else
    k = n \ 2
    a = fibo[k]
    b = fibo[BI_ADD(k + 1)]
    if even(n) then
      fiboNoMemo = BI_SUB(BI_MUL(a, BI_MUL(b, 2), a))
    end if
  end if
  fiboNoMemo = BI_ADD(BI_MUL(a, a), BI_MUL(b, b))
end function

print fiboNoMemo(78),"\n"

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 10:25 am

It's not my code. It's your code. In a different language.

Code: Select all

fiboNoMemo = n
Be sure that n is a big integer you are returning there.

Code: Select all

fibo[BI_ADD(k + 1)]
You do not want to do a big addition to k. k only ever needs to be a regualar integer.

Code: Select all

fiboNoMemo = BI_SUB(BI_MUL(a, BI_MUL(b, 2), a))
Be sure that "BI_MUL(b, 2)" is using a big integer 2.

What undef's ?

I have to dash, I'll have another look when I get back.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 4:29 pm

Confused where the array is coming from. Isn't n a simple integer?

@hippy,

Can you translate Heater's Python code to ScriptBasic?

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 5:36 pm

ScriptBasic,
Confused where the array is coming from. Isn't n a simple integer?
Yes, n is a simple integer. I see no reason for it to be a big integer. We are not about to be computing fibo(2000000000) any time soon!
Can you translate Heater's Python code to ScriptBasic?
It's not Python. It's Javascript.

Anyway, if I understand the intention of the ScriptBasic language that is not a translation of the JS.

The original and working JS looks like this:

Code: Select all

function fiboNoMemo (n) {
  if (n <= 1) {
    return BigInt(n)
  }
  let k = Math.floor(n / 2)
  let a = fibo(k);
  let b = fibo(k + 1);
  if (isEven(n)) {
    return a * ((b * BigInt(2)) - a)
  }
  return (a * a) + (b * b)
}
Notice those "return" statements there. They exit the function immediately with whatever value is in the expression following.

The last posted translation of that looks like this:

Code: Select all

function fiboNoMemo(n)
  if n <= 1 THEN
    fiboNoMemo = n
  else
    k = n \ 2
    a = fibo[k]
    b = fibo[BI_ADD(k + 1)]
    if even(n) then
      fiboNoMemo = BI_SUB(BI_MUL(a, BI_MUL(b, 2), a))
    end if
  end if
  fiboNoMemo = BI_ADD(BI_MUL(a, a), BI_MUL(b, b))
end function
Now, if I understand correctly, making an assignment to fiboNoMemo does not exit the function. It merely sets the returned value.

So, whatever this thing dose, it will run through to the end and return a value of "BI_ADD(BI_MUL(a, a), BI_MUL(b, b))". Which is not the intention and no doubt accounts for the undefs.

Perhaps it should look more like:

Code: Select all

function fiboNoMemo(n)
  if n <= 1 THEN
    fiboNoMemo = n
  else
    k = n \ 2
    a = fiboNoMemo(k)
    b = fiboNoMemo(k + 1)
    if even(n) then
      fiboNoMemo = BI_SUB(BI_MUL(a, BI_MUL(b, 2), a))
    else
      fiboNoMemo = BI_ADD(BI_MUL(a, a), BI_MUL(b, b))
    endif
  end if
end function
That's probably not correct syntax but you get the idea.

I suggest to start testing with simple cases:

fiboNoMemo(0)
fiboNoMemo(1)
fiboNoMemo(2)
fiboNoMemo(3)
...


Edit: You should of course be calling fiboNoMemo inside fiboNoMemo, not fibo as you posted. And don't foget the other suggestions I made previously.
Last edited by Heater on Fri Jun 14, 2019 5:52 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 5:45 pm

ScriptBasic wrote:
Fri Jun 14, 2019 4:29 pm
Can you translate Heater's Python code to ScriptBasic?
I'm not sure what is 'Heater's Python code'. I translated his GMP using C code example into Python, wrote my own library for using the same GMP wrapper using uint castings, and that worked for me.

That code came from viewtopic.php?f=31&t=240287&start=350#p1479349

My conversion to ScriptBasic is as follows -

Code: Select all

import bigint.bas

function bigintFibo(n)
  if (n <= 2) then
    bigintFibo = bigint::ix_let(bigint::ix_asString(bigintFibos[n]))
  else
    k = (n / 2)
    bigintFk = bigintFibo(k)
    bigintFk1 = bigintFibo(k + 1)
    if (n % 2) = 0 then
      bigintA = bigint::ix_add(bigintFk1, bigintFk1)
      bigintB = bigint::ix_sub(bigintA, bigintFk)
      bigintR = bigint::ix_mul(bigintFk, bigintB)
    else
      bigintA = bigint::ix_mul(bigintFk, bigintFk)
      bigintB = bigint::ix_mul(bigintFk1, bigintFk1)
      bigintR = bigint::ix_add(bigintA, bigintB)
    end if
    bigint::ix_free(bigintA)
    bigint::ix_free(bigintB)
    bigint::ix_free(bigintFk)
    bigint::ix_free(bigintFk1)
  end if
  bigintFibo = bigintR
end function

sub main(n)
  bigint::ix_init()

  bigintFibos[0] = bigint::ix_let("0")
  bigintFibos[1] = bigint::ix_let("1")
  bigintFibos[2] = bigint::ix_let("1")

  bigintF = bigintFibo(n)
  bigintF10 = bigint::ix_base(bigintF, 10)
  print bigint::ix_asString(bigintF10)
  bigint::ix_free(bigintF10)
  bigint::ix_free(bigintF)

  bigint::ix_free(bigintFibos[0])
  bigint::ix_free(bigintFibos[1])
  bigint::ix_free(bigintFibos[2])

  bigint::ix_clear()
end sub

main(2)
But, after frustrating battles with unhelpful error messages in doing that, I just get -

Code: Select all

pi@Pi3B:~/extensions $ scriba bigintfibo.sb
(0): error &H35:Mandatory argument is missing
You're welcome to debug that but I just don't have the time or inclination.

If you tell me what needs to change I'll make that edit and run it again, but I suspect, for things over bigintFibo(2) it's going to give the double freeing issue as your translation did.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 5:50 pm

More than likely you're passing a UNDEF variable to GMP.

Simple BIGINT math seems to be working using the extension module I posted. If the fibo is going to look that ugly, I don't think anyone will use it.
Last edited by ScriptBasic on Fri Jun 14, 2019 5:59 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 5:57 pm

ScriptBasic wrote:
Fri Jun 14, 2019 5:50 pm
More than likely you're passing a UNDEF variable to GMP.
I don't see where but, as said, if you want to debug it and determine where the issue is; I'll fix it and try again.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 6:00 pm

Can you post your extension module code?

My version of the GMP extension module uses strings to store BIGINT values. The GMP library ADD, SUB and MJL does math on these numeric strings.

Your LET is confusing to me.
Last edited by ScriptBasic on Fri Jun 14, 2019 6:11 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 6:09 pm

This is getting messy.

Posting code snippets back and forth, in different languages, is confusing.

It would go easier if ScriptBasic including the current big integer extension module were in a Github repo that we could clone and play with. Or perhaps BitBucket or whatever.

At the end of the day the fibo equations we have been using are very simple.

I'd start testing with some simple x * y stuff.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 6:15 pm

ScriptBasic wrote:
Fri Jun 14, 2019 6:00 pm
Can you post your extension module code?
That's all here - viewtopic.php?f=31&t=240287&start=350#p1479573

The only change was to add a "-lgmp" into interface.c so it would link with the gmp library.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 6:16 pm

The current SB GMP extension module code is on RaspberryBASIC.org forum. I'll push it to the ScriptBasic Extensions Sandbox today. it's the same code I have been posting here.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 6:29 pm

Yeah, yeah but a linking us to a git repo would be better.

You know:

Code: Select all

$ git clone https://github.com/ScriptBasic/ScriptBasic.git
$ cd ScriptBasic
$ ./configure
$ make
$ sudo make install
Then:

Code: Select all

$ cd 
$ scriba fibo.bas

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 6:41 pm

ScriptBasic wrote:
Fri Jun 14, 2019 6:00 pm
Your LET is confusing to me.
This one ... ?

Code: Select all

bigintFibo = bigint::ix_let(bigint::ix_asString(bigintFibos[n]))
::ix_let expects a string as a parameter, ::ix_asString converts the bigintFibo[n] to that string.

Because bigintFibos[n] isn't a string, it's a pointer, which happens to be a integer/long in the case of Python/ScriptBasic. One cannot pass a pointer/integer/long into my library when it is expecting a string.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 7:01 pm

jahboater wrote:
Fri Jun 14, 2019 7:06 am
The problem is, as always, mixing two languages where one language has a richer choice of data types than the other.
Rather than converting the big numbers back and forth between strings, it would be more efficient (and probably less error prone) to pass back a handle in the form of an integer and let the C code keep track of the GMP big numbers to which each handle corresponds.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 7:12 pm

I would like to keep BIGINT in base 10 numeric strings. This will allow me to scale down a BIGINT environment by dividing it and using standard math functions for further processing. GMP is a BIGINT transport library in a sense.
Last edited by ScriptBasic on Fri Jun 14, 2019 7:17 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 7:15 pm

Of course that integer "handle" could just be a pointer :)

But, my demo in C shows that it can be done with the "user space" program only ever seeing stings. Performance was up there with some other languages. Given that most of the work is in the big arithmetic ScriptBasic should be up there with them.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 8:36 pm

Here is my latest attempt.

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)
  if n <= 2 THEN
    hfibo = n
  else
    k = n / 2
    fk = hfibo(k)
    fk1 = hfibo(BI_ADD(k, 1))
    if n % 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

SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1

PRINT hfibo(78),"\n"
It returns zero. :o

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 8:54 pm

This non-GMP version also prints zero. Lets try to get this non-BIGINT version going first.

Code: Select all

function hfibo(n)
  if n <= 2 THEN
    hfibo = n
  else
    k = n / 2
    fk = hfibo(k)
    fk1 = hfibo(k + 1)
    if n % 2 = 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

SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1

PRINT hfibo(78),"\n"

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 9:02 pm

ScriptBasic wrote:
Fri Jun 14, 2019 8:54 pm
This non-GMP version also prints zero. Lets try to get this non-BIGINT version going first.

Code: Select all

function hfibo(n)
  if n <= 2 THEN
    hfibo = n
  else
    k = n / 2
    fk = hfibo(k)
    fk1 = hfibo(k + 1)
    if n % 2 = 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

SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1

PRINT hfibo(78),"\n"
Try changing

k = n / 2

to

k = int(n / 2)

and see if that helps.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 9:04 pm

Heater wrote:
Fri Jun 14, 2019 7:15 pm
Of course that integer "handle" could just be a pointer :)
It is.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 9:07 pm

I changed it to

k = n \ 2

Integer divide and still returns zero.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 9:23 pm

hippy wrote:
Fri Jun 14, 2019 9:04 pm
Heater wrote:
Fri Jun 14, 2019 7:15 pm
Of course that integer "handle" could just be a pointer :)
It is. The casting has to be done within the library because it cannot be done in Python.
The advantage of using integer handles that are not pointers is that one can get by with a much smaller number of bits. This enables sensible range checking to avoid segmentation faults and increases compatibility with languages that don't support integers the size of pointers. Luckily lci has not implemented the semantics for

I CAN HAS GMP?

in a way that would allow dynamic linking to external subroutine libraries.

When a programming language lacks the expressive power necessary to convey an algorithm as complicated as Karatsuba efficiently to the processor, it is liberating to be able to call subroutines written in other languages. At the same time, the requirement to master multiple languages makes it more difficult to avoid the digital apocalypse.
Last edited by ejolson on Fri Jun 14, 2019 9:34 pm, edited 6 times in total.

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 9:25 pm

ScriptBasic wrote:
Fri Jun 14, 2019 9:07 pm
I changed it to

k = n \ 2

Integer divide and still returns zero.
What happens if you change the line

hfibo = n

to

r = n

near the beginning of the hfibo function?

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 9:33 pm

It's printing a negative value.

Code: Select all

function hfibo(n)
  if n <= 2 THEN
    r = n
  else
    k = n \ 2
    fk = hfibo(k)
    fk1 = hfibo(k + 1)
    if n % 2 = 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

SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1

PRINT FORMAT("%.f",hfibo(78)),"\n"
jrs@jrs-laptop:~/sb/GMP$ scriba nfibo.sb
-45717905866441093021696
jrs@jrs-laptop:~/sb/GMP$

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

Re: A Final Fibonacci Challenge

Fri Jun 14, 2019 9:35 pm

ScriptBasic wrote:
Fri Jun 14, 2019 9:33 pm
It's printing a negative value.

Code: Select all

function hfibo(n)
  if n <= 2 THEN
    r = n
  else
    k = n \ 2
    fk = hfibo(k)
    fk1 = hfibo(k + 1)
    if n % 2 = 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

SPLIT "0,0,0,0,0,0" BY "," TO k, a, b, r, fk, fk1

PRINT FORMAT("%.f",hfibo(78)),"\n"
jrs@jrs-laptop:~/sb/GMP$ scriba nfibo.sb
-45717905866441093021696
jrs@jrs-laptop:~/sb/GMP$
Does F(31) work?
Last edited by ejolson on Fri Jun 14, 2019 10:00 pm, edited 2 times in total.

Return to “General programming discussion”