search

ckrause / loda

LODA is an assembly language, a computational model and a tool for mining integer sequence programs.
Apache License 2.0
20 stars 5 forks source link

Number format with arbitrary precision #44

Closed ckrause closed 3 years ago

ckrause commented 3 years ago

We currently use 64-bit signed ints as number format. Many of the sequence terms in the OEIS exceed this size. We should check if there are libraries for big number formats or if it is feasible to implement it ourselves.

karttu commented 3 years ago

There are several, for example GMP (GNU Multiple Precision Arithmetic Library), but I don't know about their current status. Note that with any bignum-implementation comes the added headache of the need to allocate and deallocate lists, possibly largish. (OTOH, with only two 64-bit words we already go up to 340282366920938463463374607431768211456, unsigned). But with well-designed interfaces that kind of change might be mostly transparent (coding-wise), except perhaps in the execution times and memory usage? But I'm not an expert in C++, so I don't know all of its perks.

ckrause commented 3 years ago

I don't think we don't need arbitrary precision. I was thinking to use C++ templates with std::arrays. That should be much more efficient, because everything is stored directly on the stack.

jonmaiga commented 3 years ago

I've had decent success with the trio mpir+mprf+mpreal. If you are aiming for integer only operations mpir might suffice (e.g. mpz_class) or possibly own implementation/other lightweight library.

(Great project btw!)

neoneye commented 3 years ago

For evaluating programs with bigger number you can use LODA Lab. However this cannot do mining of new programs.

PROMPT> loda eval A42 -t 19 
1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111,1111111111111,11111111111111,111111111111111,1111111111111111,11111111111111111,111111111111111111,1111111111111111111

PROMPT> loda-lab eval 42 -t 40
1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111,1111111111111,11111111111111,111111111111111,1111111111111111,11111111111111111,111111111111111111,1111111111111111111,11111111111111111111,111111111111111111111,1111111111111111111111,11111111111111111111111,111111111111111111111111,1111111111111111111111111,11111111111111111111111111,111111111111111111111111111,1111111111111111111111111111,11111111111111111111111111111,111111111111111111111111111111,1111111111111111111111111111111,11111111111111111111111111111111,111111111111111111111111111111111,1111111111111111111111111111111111,11111111111111111111111111111111111,111111111111111111111111111111111111,1111111111111111111111111111111111111,11111111111111111111111111111111111111,111111111111111111111111111111111111111,1111111111111111111111111111111111111111

(LODA is indeed a great project!)

ckrause commented 3 years ago

I added native support for big numbers in LODA. No external libraries are used. There is an upper limit of the size (configurable at compile time). Currently we support up to 180 decimal digits. Still room for performance improvements:

2021-08-01 16:33:18|INFO |Starting operations benchmark
2021-08-01 16:33:18|INFO |mov: 0.079µs
2021-08-01 16:33:18|INFO |add: 0.159µs
2021-08-01 16:33:18|INFO |sub: 0.279µs
2021-08-01 16:33:18|INFO |trn: 0.392µs
2021-08-01 16:33:18|INFO |mul: 2.369µs
2021-08-01 16:33:18|INFO |div: 15.448µs
2021-08-01 16:33:18|INFO |dif: 19.218µs
2021-08-01 16:33:19|INFO |mod: 19.025µs
2021-08-01 16:33:19|INFO |pow: 89.842µs
2021-08-01 16:33:20|INFO |gcd: 583.418µs
2021-08-01 16:33:20|INFO |bin: 36.602µs
2021-08-01 16:33:20|INFO |cmp: 0.028µs
2021-08-01 16:33:20|INFO |min: 0.128µs
2021-08-01 16:33:20|INFO |max: 0.117µs
neoneye commented 3 years ago

Awesome.