Recent

Author Topic: BigNumbers: yet another library for calculating with very big natural numbers  (Read 25074 times)

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Flying Sheep Inc. is proud to present the BigNumber library.

The library provides a class TNumber that can handle Natural numbers of up to 2147483648 digits long (provided you have the memory to store the result in memory)

This allows for a range larger than the Float type, and without loss of precision.

Ever needed (or wanted) to calculate 9^99 with absolute precision?
Answer:
Code: [Select]
29512665430652752148753480226197736314359272517043832886063884637676943433478020332709411004889)
or Fac(100)?
Answer:
Code: [Select]
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
In that case: this is the library to use.

The library also provides conversion functions from and to Hexadecimal and Binary.

Checkout the code (including all dependencies) from my svn repository:

Code: [Select]
svn co http://svn.code.sf.net/p/flyingsheep/code/trunk/wtf /some/path/on/your/computer

Or browse the svn repository at: http://sourceforge.net/p/flyingsheep/code/HEAD/tree/trunk/wtf/

Features:
  • TNumber supports almost infinite big numbers with absolute precision calulation
  • TNumber supports threadsafe caching of operations, with options to lock and unlock the cache
  • Caching can be local to the instance or shared with other instances
  • Caching can be turned on and off on the fly (default at creation is caching: on)
  • TNumber supports object oriented boolean type handling (see the BoolFactory unit for details)
  • TNumber accepts decimal, hexadecimal and binary input to set it's value
  • TNumber provides a callback event for very long calculations, thus providing the means to update the GUI
  • In the true spirit of FreePascal, this library is fully OS and Platform independant
  • Unfortunately the library does not (and will not either in future) work perfectly in programs that use TP mode {$mode tp}

BigNumbers needs the following units (all provided at the svn repository as mentioned above):
  • NCalc
  • Expressions
  • BoolFactory
  • NumberOperationsCache

Bugs or enhancements can be reported here on the forum.
When the time is ripe, this library may ver well become part of the FCL.

Bart

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
The boolfactory unit looks like something out of an obfuscated * contest :-)

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
The boolfactory ....

Pssssssssssssssssssssst  O:-)

Bart

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
(I btw didn't look further when I saw the unit was hardwired for decimal and did dynamic memory allocation on every operation)

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
(I btw didn't look further when I saw the unit was hardwired for decimal and did dynamic memory allocation on every operation)

Ah well, allowing for up yo 2G digits has it's price.
(The foldername should give real coders a clue about certain pculiarities ...)
It wouldn't be nice to claim several times 2 G space alone for the cache, would it.
I still need to find out if (100)^(100^100) fits int that memory space.
IIRC then this would amout to more digits than there are stars in the universe.
Also recall this number has a specila name, but just can't find it right now, but I'm getting off topic.

Bart

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Update: Implemented SqrtN() function.

Bart

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
I still need to find out if (100)^(100^100) fits int that memory space.
IIRC then this would amout to more digits than there are stars in the universe.
Also recall this number has a special name, but just can't find it right now, but I'm getting off topic.

It seems I was looking for Googolplex , which is 10^Googol, where Googol = 10^100.
So, that should be a 1 with 10^100 zeroes...., and that should fit in my TNumber type.
(It is written out here.)
Even Googol is a number so big, it is more than the number of hydrogen atoms in the observable universe it seems.

Bart
« Last Edit: September 14, 2013, 04:31:46 pm by Bart »

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Added RandomN and RandomRangeN functions.

eny

  • Hero Member
  • *****
  • Posts: 1634
Checkout the code (including all dependencies) from my svn repository:

Code: [Select]
svn co http://svn.code.sf.net/p/flyingsheep/code/trunk/wtf /some/path/on/your/computer

Or browse the svn repository at: http://sourceforge.net/p/flyingsheep/code/HEAD/tree/trunk/wtf/
I'm not sure if a folder named 'wtf' will contribute to significantly increasing the download count...
All posts based on: Win10 (Win64); Lazarus 2.0.10 'stable' (x64) unless specified otherwise...

jarto

  • Full Member
  • ***
  • Posts: 106
Bart, have you made any tests at how fast your library is compared with other big integer libraries? I'm mainly asking this as I've been improving encryption code in LockBox2, which has its own big integer library. While I was able to speed up the code that creates RSA keys, it still takes quite a while to create 2048 bit or larger keys.

The algorithm that does the job is Miller-Rabin primality test. The algorithm is described as pseudocode here: http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

LockBox2's version of Miller-Rabin is fuction LbBiIsCompositFast in LbBigInt.pas. Latest reposity is https://github.com/jarto/lockbox2

If your code is faster, it'd be interesting to use it for a better RSA implementation.

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #10 on: September 15, 2013, 11:23:36 pm »
@Jarto: first of all, please read the PM I sent you!

The algorithm is described as pseudocode here: http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

That page is jibberish to me.
Mind you that my library does only Natural numbers.
The page looked like it neede more.

If you understand the algorithm I'm afraid speed testing is up to you.
First and formost I implemented it to be accurate and clean (as in: easy to understand, anybody with basic undersatnding of math can understand it) code, so some (maybe many) things may be improved speedwise.

Bart
« Last Edit: September 16, 2013, 12:00:34 am by Bart »

Mike.Cornflake

  • Hero Member
  • *****
  • Posts: 1260
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #11 on: September 16, 2013, 03:00:22 am »
Quote
It seems I was looking for Googolplex , which is 10^Googol, where Googol = 10^100.
So, that should be a 1 with 10^100 zeroes...., and that should fit in my TNumber type.
(It is written out here.)
Superb :-)  Page has been loading for over a minute now, that's a LOT of zero's.  I'm wondering if my browser will run out of memory before that page finishes loading :-)

BTW: Many thanks for the library.  Can't see me using it, but good to know it's there :-)
Lazarus Trunk/FPC Trunk on Windows [7, 10]
  Have you tried searching this forum or the wiki?:   http://wiki.lazarus.freepascal.org/Alternative_Main_Page
  BOOKS! (Free and otherwise): http://wiki.lazarus.freepascal.org/Pascal_and_Lazarus_Books_and_Magazines

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #12 on: September 18, 2013, 04:37:52 pm »
Added conversion to and from Roman numerals, the latter making more sense than the StrUtils.RomanToInt that accepts ridiculous values like 'MDCLXVIVXLCDM' or 'IIIM'.

Bart

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #13 on: September 18, 2013, 04:39:20 pm »
Quote
It seems I was looking for Googolplex , which is 10^Googol, where Googol = 10^100.
So, that should be a 1 with 10^100 zeroes....,
..., that's a LOT of zero's.

Added Googol and GoogolPlex to the library.

Bart

BigChimp

  • Hero Member
  • *****
  • Posts: 5740
  • Add to the wiki - it's free ;)
    • FPCUp, PaperTiger scanning and other open source projects
Re: BigNumbers: yet another library for calculating with very big natural numbers
« Reply #14 on: September 18, 2013, 04:44:21 pm »
Added conversion to and from Roman numerals, the latter making more sense than the StrUtils.RomanToInt that accepts ridiculous values like 'MDCLXVIVXLCDM' or 'IIIM'.
Mmmm... you're tempting me to locate some list of Latin inscriptions and find one that does have such ridiculous values... AFAIR, not everybody went by the same rules when taking hammer and chisel - not surprising given that inscriptions vary between 100s of years BC and say 1900... or even later...
Want quicker answers to your questions? Read http://wiki.lazarus.freepascal.org/Lazarus_Faq#What_is_the_correct_way_to_ask_questions_in_the_forum.3F

Open source including papertiger OCR/PDF scanning:
https://bitbucket.org/reiniero

Lazarus trunk+FPC trunk x86, Windows x64 unless otherwise specified

 

TinyPortal © 2005-2018