Status of Ada bignum (former Odd k for which k+2^m is composite for all m < k) Rosetta Code)

General
1

What is the status of Rosetta Code implementation of “Odd k for which k+2^m is composite for all m < k)”?

I am asking because I am considering implementing unbounded integer arithmetic with the goals:

  • Advanced memory management preventing excessive copying;
  • In-place operations (e.g. for addition);
  • Long to short operations;
  • More operations, e.g. Square, Sqrt, 2**N, Bit slice
  • Advanced algorithms (e.g. Karatsuba multiplication and squaring);
  • No limit on the number size (except for storage pool limits).

Any comments.

1 Like
2

Will it have SPARK mode on?

3

No. Simple Components are kept Ada 95.

1 Like
4

Hi Dmitry;

I have not made any more progress on this Rosetta Code task. I would be thrilled to see your unbounded integer arithmetic addition to your Simple Components.

RBE

5

Thanks, it would take time though.

Meanwhile, you could improve your Is_Prime implementation. The end test Big_Temp * Big_Temp <= N alone is a killer! Multiplication is a most expensive operation. No wonder it runs forever especially because the standard library implementation is O(N**2). But with all tricks like Karatsuba or FFT you would not squeeze much out, no way.

I glanced at the implementation in Ada Crypto (GitHub - cforler/Ada-Crypto-Library: This project is obsolete is no longer developed, maintained or serviced!), it tabulates first four-digit primes! :sunglasses: The implementation is understandable.

The GMP implementation is quite hard to digest. The code is messy even according to low C standards!

Which one is numerically faster I cannot tell.

I think these two could serve as the major inspiration sources. After all you need it as strong as to make the solution work and not an ounce stronger! :grinning:

6

I have also not made any more progress with respect to the last code snipped I posted in the thread… I left it running for several hours but it never actually found the first number (it has to find a huge factor that takes forever).

Its performance was about 4 times lower than the JS library used in the website I liked to compare it to. I saw that the JS implementation had also created a large array that it was using to quickly find out primes… Plus I suppose the JS engine has a greatly (near machine-level) optimised Big_Num library… And the algorithm looked a bit more sophisticated also.

That is all I can say about it right now :slight_smile:

Best,
Fer

7

BTW, there are at least two Rosetta Code Tasks written in Ada already which use the Ada-Crypto-Library. These I was unable to compile (don’t have the error logs handy).

So it would be nice to have all Ada solutions on the Rosetta Code web site to be working solutions… :slight_smile:

Also, I am looking at PrimeSieve (C/C++ library) to see if a thin (or thick) binding can be made, but I don’t think that it will work for big integers. Also there is the “ntheory” Perl module (written in C) which supposedly as “infinite” unlimited integer size (based on how much RAM you have I guess). But that would be a very challenging library to make an Ada binding for. (bad grammar here)

RBE