If it is then your understanding is wrong. Where would you get that idea from? I know of no languages that use GMP that have memory leaks apart from ScriptBaisc and it's GMP extension.Is it my understanding all fibos using GMP leak?
I doubt it. It's probably done very differently in Python. For example simply maintaining big numbers as normal GMP objects rather than endlessly converting to and from strings which is very inefficient.The answer may be looking at the GMP extension module for Python.
Heater wrote: If it is then your understanding is wrong. Where would you get that idea from? I know of no languages that use GMP that have memory leaks apart from ScriptBaisc and it's GMP extension.
Dr. Jekyll / Hyde,Heater wrote: As it turns out I'm having the same issue with using my big integer functions in C++ from Javascript. Works fine but does not seem to clean up memory.
No, I did not. I said I have a memory problem with my home made big integer class in Javascript. I don't have anything that uses GMP from Javascript.You said your JavaScript GMP fibo leaked.
Yes it is. What else could a problem in ScriptBasic's use of the GMP library be?This isn't a ScriptBasic issue only.
Since when is reporting bugs considered "trashing"?Stop trashing SB for your enjoyment.
Code: Select all
PyDoc_STRVAR(doc_fib,
"fib(n) -> mpz\n\n"
"Return the n-th Fibonacci number.");
static PyObject *
Pygmpy_fib(PyObject *self, PyObject *other)
{
PympzObject *result;
mpir_si n;
n = SI_From_Integer(other);
if ((n == -1) && PyErr_Occurred()) {
TYPE_ERROR("fib() requires 'int' argument");
return NULL;
}
else if (n < 0) {
VALUE_ERROR("Fibonacci of negative number");
return NULL;
}
else {
if (!(result = (PympzObject*)Pympz_new()))
return NULL;
mpz_fib_ui(Pympz_AS_MPZ(result), n);
}
return (PyObject*)result;
}
PyDoc_STRVAR(doc_fib2,
"fib2(n) -> tuple\n\n"
"Return a 2-tuple with the (n-1)-th and n-th Fibonacci numbers.");
static PyObject *
Pygmpy_fib2(PyObject *self, PyObject *other)
{
PyObject *result;
PympzObject *fib1 = 0, *fib2 = 0;
mpir_si n;
n = SI_From_Integer(other);
if ((n == -1) && PyErr_Occurred()) {
TYPE_ERROR("fib2() requires 'int' argument");
return NULL;
}
else if (n < 0) {
VALUE_ERROR("Fibonacci of negative number");
return NULL;
}
else {
CREATE_TWO_MPZ_TUPLE(fib1, fib2, result);
mpz_fib2_ui(fib1->z, fib2->z, n);
}
PyTuple_SET_ITEM(result, 0, (PyObject*)fib1);
PyTuple_SET_ITEM(result, 1, (PyObject*)fib2);
return result;
}
Code: Select all
def fibo(n):
if n <= 0:
return 0
if use_gmp:
a = mpz(0)
b = mpz(1)
else:
a = 0
b = 1
numbits = int(math.log(n,2))
for i in range(numbits,-1,-1):
d = a*(b*2-a)
e = a*a+b*b
if (n >> i) & 1:
a = e
b = d + e
else:
a = d
b = e
return a
Code: Select all
def fibo(n):
if n <= 0:
return 0
if use_gmp:
a = mpz(0)
b = mpz(1)
else:
a = 0
b = 1
numbits = int(math.log(n,2))
for i in range(numbits,-1,-1):
if i > 0:
d = a*(b*2-a)
e = a*a+b*b
if (n >> i) & 1:
a = e
b = d + e
else:
a = d
b = e
else:
if n & 1:
d = a*a+b*b
else:
d = a*(b*2-a)
return d
Code: Select all
[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n
Fibonacci(4784969) calculation took 0.4217264652252197 seconds
[email protected]:~/fibochallenge $ ./fibo_rdr.py -t -n
Fibonacci(4784969) calculation took 0.4217088222503662 seconds
[email protected]:~/fibochallenge $ ./fibo_fd.py -t -n
Fibonacci(4784969) calculation took 0.5097312927246094 seconds
[email protected]:~/fibochallenge $ ./fibo_fdi.py -t -n
Fibonacci(4784969) calculation took 0.3734128475189209 seconds
Code: Select all
[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n -i
Fibonacci(4784969) calculation took 10.606588363647461 seconds
[email protected]:~/fibochallenge $ ./fibo_rdr.py -t -n -i
Fibonacci(4784969) calculation took 10.56157374382019 seconds
[email protected]:~/fibochallenge $ ./fibo_fd.py -t -n -i
Fibonacci(4784969) calculation took 13.833927631378174 seconds
[email protected]:~/fibochallenge $ ./fibo_fdi.py -t -n -i
Fibonacci(4784969) calculation took 9.754611492156982 seconds
That's a nice roundup of Python codes. I'll run them through fibench on the super-cheap cluster to see what happens. With all the Pi 4B excitement, it seems the updated JavaScript codes are somewhat delayed. Fortunately, the Pi Zero is still state of the art for a computer that comes free with a magazine subscription. I wonder if there will ever be a replacement with a single-core Cortex-A53, smaller process size and less requirements for electricity.
It would be interesting to see which of those hand-coded big-number multiplication algorithms run faster (or slower) on the new hardware. Given these preliminary results for the merge sort (perhaps due only to different compiler optimization settings), I'm not sure what to expect.
Ah, sorry about that.With all the Pi 4B excitement, it seems the updated JavaScript codes are somewhat delayed.
Nice one!gkreidl wrote: ↑Wed Jun 26, 2019 7:37 amThe main reason is, that it calculates one more (large) Fibonacci number than we really need. To get fibo(4784969) it also calculates fibo(4784970), which is costly. This can be easily avoided as shown below.
This version is a bit faster than the recursive doubling version for many numbers and at least not slower for others. And it also uses less memory. It should be easily adaptable to any other programming language.Code: Select all
def fibo(n): if n <= 0: return 0 if use_gmp: a = mpz(0) b = mpz(1) else: a = 0 b = 1 numbits = int(math.log(n,2)) for i in range(numbits,-1,-1): if i > 0: d = a*(b*2-a) e = a*a+b*b if (n >> i) & 1: a = e b = d + e else: a = d b = e else: if n & 1: d = a*a+b*b else: d = a*(b*2-a) return d
Code: Select all
\
\ Fibonacci with million digits
\
: bits? \ n -- nbits-1
n:ln 2 n:ln n:/ n:int ;
: fibo-loop
>r \ Put loop counter on r-stack
\ a b
2dup 2 n:* \ a b a 2b
over n:- \ a b a (2b-a)
n:* -rot \ d=(2b-a)*a a b
n:sqr swap n:sqr n:+ \ d=(2b-a)*a e=b*b+a*a
r> [email protected] swap n:shr 1 n:band if
dup \ a b b
rot \ b b a
n:+ \ b c=b+a
then ;
: fibo \ n -- fibo(n)
>r \ Put n on r-stack
F0 F1 \ a b
' fibo-loop 1 [email protected] bits? loop-
\ a b
r> 1 n:band if
n:sqr swap n:sqr n:+ \ b*b+a*a
else
2 n:* over n:- n:* \ (2b-a)*a
then ;
: app:main
d:msec >r
4784969 fibo
"%.f" strfmt \ Convert result to just an 'int' string.
d:msec r> n:- >r
s:len . " digits:" . cr
. cr
r> . " msec" . cr
bye ;
Here is my old Basic version adapted to use gkreidl's approach. You need to change just a few lines for the JavaScript conversion you did from my old Basic source. Just remember to change all uint's to BIGINT's. Let me know how it performs vs your recursive fibo.
Code: Select all
func log2(double n), double
return log(n)/log(2)
endf
func fibo(int n),uint
uint a = 0
uint b = 1
int numbits = int(log2(n))
for i = numbits to 1 step -1
uint d = a*(b*2-a)
uint e = a*a+b*b
a = d
b = e
if (n >> i) & 1
uint c = a+b
a = b
b = c
endif
next i
if n & 1
a = a*a + b*b
else
a = a*(b*2-a)
endif
return a
endf
Code: Select all
def fibo(n):
if n <= 0:
return 0
if use_gmp:
a = mpz(0)
b = mpz(1)
else:
a = 0
b = 1
numbits = int(math.log(n,2))
for i in range(numbits,0,-1):
d = a*(b*2-a)
e = a*a+b*b
if (n >> i) & 1:
a = e
b = d + e
else:
a = d
b = e
if n & 1:
return a*a+b*b
else:
return a*(b*2-a)
fibo(5000000) has 1735013 set bits
Nonsense.
Yes, but that was not the question.
Code: Select all
[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n 4194320
Fibonacci(4194320) calculation took 0.2915217876434326 seconds
[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n 4194319
Fibonacci(4194319) calculation took 0.3306257724761963 seconds
Interesting.gkreidl wrote: ↑Fri Jul 05, 2019 6:56 amHaving more "1"s in the lowest bits is important.4194320 = 0x400010Code: Select all
[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n 4194320 Fibonacci(4194320) calculation took 0.2915217876434326 seconds [email protected]:~/fibochallenge $ ./fibo_rd.py -t -n 4194319 Fibonacci(4194319) calculation took 0.3306257724761963 seconds
4194319 = 0x40000f