Liberation through Computer Literacy

[John_Spikowski]

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]

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.

[John_Spikowski]

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

@hippy,

Can you translate Heater's Python code to ScriptBasic?

[Heater]

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.

[hippy]

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.

[John_Spikowski]

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.

[hippy]

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]

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.

[Heater]

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]

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]

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]

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]

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]

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]

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.

[Heater]

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.

[John_Spikowski]

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.

[John_Spikowski]

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]

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]

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

It is.

[John_Spikowski]

I changed it to

k = n \ 2

Integer divide and still returns zero.

[ejolson]

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.

[ejolson]

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]

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]

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?