## Liberation through Computer Literacy

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

### Re: A Final Fibonacci Challenge

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

### Re: A Final Fibonacci Challenge

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

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

### Re: A Final Fibonacci Challenge

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

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

### Re: A Final Fibonacci Challenge

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
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)
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 = bigint::ix_let("0")
bigintFibos = bigint::ix_let("1")
bigintFibos = 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)
bigint::ix_free(bigintFibos)
bigint::ix_free(bigintFibos)

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.

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

### Re: A Final Fibonacci Challenge

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 John_Spikowski on Fri Jun 14, 2019 5:59 pm, edited 1 time in total.

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

### Re: A Final Fibonacci Challenge

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.

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

### Re: A Final Fibonacci Challenge

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 John_Spikowski on Fri Jun 14, 2019 6:11 pm, edited 1 time in total.

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

### Re: A Final Fibonacci Challenge

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

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

### Re: A Final Fibonacci Challenge

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.

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

### Re: A Final Fibonacci Challenge

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

### Re: A Final Fibonacci Challenge

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

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

### Re: A Final Fibonacci Challenge

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: 8611
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

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.

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

### Re: A Final Fibonacci Challenge

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 John_Spikowski on Fri Jun 14, 2019 7:17 pm, edited 1 time in total.

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

### Re: A Final Fibonacci Challenge

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

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)
if n % 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

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

PRINT hfibo(78),"\n"
``````
It returns zero. John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA

### Re: A Final Fibonacci Challenge

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: 8611
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

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

### Re: A Final Fibonacci Challenge

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

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

### Re: A Final Fibonacci Challenge

I changed it to

k = n \ 2

Integer divide and still returns zero.

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

### Re: A Final Fibonacci Challenge

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: 8611
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

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?

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

### Re: A Final Fibonacci Challenge

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: 8611
Joined: Tue Mar 18, 2014 11:47 am

### Re: A Final Fibonacci Challenge

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.