Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Dark GDK / An integer of unlimited size

Author
Message
Michael P
18
Years of Service
User Offline
Joined: 6th Mar 2006
Location: London (UK)
Posted: 5th Oct 2008 18:51
I'm looking at ways to create a proper prime number generator that would be capable of finding very large prime numbers with for example, 14 million digits. I know such generators already exist, I just want to have a go at making one myself

The first obvious problem is that in C++ integers are limited in size. Does anybody know of a way in which I could deal with such large numbers and perform basic mathematical operations on them in C++?
SushiBox
16
Years of Service
User Offline
Joined: 20th Sep 2008
Location: Ohio
Posted: 5th Oct 2008 19:54
A Russian computer scientist came up with this C++ class for integers of unlimited size.

Its right up your alley. Although some of a documentation is still in Russian, shouldn't be too hard to check out.

http://www.imach.uran.ru/cbignum/

www.Helios-Online.net
Michael P
18
Years of Service
User Offline
Joined: 6th Mar 2006
Location: London (UK)
Posted: 6th Oct 2008 21:47 Edited at: 6th Oct 2008 21:48
Thanks. However, I want to have a go at writing something similar to that myself before I move onto other people's stuff.

I think a good place to start would be working out how the bytes of an integer come to form a number. The below code allows me to look at the individual bytes of each integer and find a relationship between them; it is more useful in debug mode. I spent a while trying to find a formula between the bytes but couldn't find one that would work for all possible integers.

Does anyone know what formula is used to turn 4 bytes into an integer?

IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 6th Oct 2008 22:52
To be honest, if you don't know the basic storage layouts of bytes, words, dwords and maybe even qwords on Intel, then it's not likely you'll be able to code this yourself without a lot of revision.

Check the wiki pages for twos-complement, signed number representations, endianness (intel is little-endian), then start looking elsewhere for number layouts in memory and large-number handling.

Lilith
16
Years of Service
User Offline
Joined: 12th Feb 2008
Location: Dallas, TX
Posted: 7th Oct 2008 00:03
Quote: "Does anyone know what formula is used to turn 4 bytes into an integer?"


As the saying goes, "Words is words." Aside from the bit position representing a power of 2, there is no formula for integers. There's a format for floats because they aren't naturally represented by binary data.

Integers is integers.

Lilith, Night Butterfly
I'm not a programmer but I play one in the office
SushiBox
16
Years of Service
User Offline
Joined: 20th Sep 2008
Location: Ohio
Posted: 7th Oct 2008 01:06
Completely off topic, but reminds me of something my engineering instructor said.

"4 bits is a nibble, 8 bits is a byte, then all the sudden 1024 bytes is a kb, and im like what the f***?".

www.Helios-Online.net
Mahoney
16
Years of Service
User Offline
Joined: 14th Apr 2008
Location: The Interwebs
Posted: 7th Oct 2008 03:08
Quote: "Does anyone know what formula is used to turn 4 bytes into an integer?"


I'm not sure if I know what you mean, but I'll give it a go.

The value is interpreted from a binary value. The 4 bytes are really 32-bits put together. So, for the value 283, you get the binary:

0000 0000 0000 0000 0001 0001 1011

That's unsigned. Signed, it's a little different. Read over some of this (Chapter 1, specifically); it explains it all.

http://www.arl.wustl.edu/~lockwood/class/cs306/books/artofasm/toc.html

Windows Vista Home Premium Intel Pentium Dual-Core 1.6 Ghz 1GB DDR2 RAM GeForce 8600GT Twin Turbo
SushiBox
16
Years of Service
User Offline
Joined: 20th Sep 2008
Location: Ohio
Posted: 7th Oct 2008 20:29
Ok, I understand you want to do this your self... But an algorithim for generating prime numbers of such length is EXTREMELY complex and the only instances I can find of this being done, is from universities etc.

Depending on the level of math you are capable of comprehending, the MOST custom way you can do this. Is at least use the NTL. It stands for Number Theory Library. Here is a link: http://www.shoup.net/ntl/

Someone made a large prime number generator with this that got around what you need it for.

"NTL is a high-performance, portable C++ library providing data structures and algorithms for manipulating signed, arbitrary length integers, etc." Source: http://www.shoup.net/ntl

Sorry to break the news, I cant think of a single way to do this without extremely complex data structures.

www.Helios-Online.net
Diggsey
18
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 7th Oct 2008 20:46 Edited at: 7th Oct 2008 20:47
To convert an integer to a string, do this:
1. Divide by ten
2. Multiply by ten and subtract from original number
3. Use a 'switch' statement to convert the digit to '0','1','2',etc.
4. Put this digit at start of result string
5. If number produced by step 1 was non-zero, set as original number and go to 1.

[b]Yuor signutare was aresed by a deslyxic mud...
BOX2D V2 HAS HELP FILES! AND A WIKI!
Michael P
18
Years of Service
User Offline
Joined: 6th Mar 2006
Location: London (UK)
Posted: 7th Oct 2008 20:53 Edited at: 7th Oct 2008 20:57
I agree with SushiBox, this is way beyond me

I did have some success though; I worked out how to take the bytes of an int and calculate the int manually. The below code demonstrates this and the key line is:


Full code:


Expanding on the above by adding in more bytes, the maximum size of the number could be increased.
Benjamin
22
Years of Service
User Offline
Joined: 24th Nov 2002
Location: France
Posted: 7th Oct 2008 21:13
If you have the bytes in an array then you already have an integer:



Michael P
18
Years of Service
User Offline
Joined: 6th Mar 2006
Location: London (UK)
Posted: 7th Oct 2008 21:32
The idea behind it was that by looking at how those bytes come to form the number within an int, I can find a way of storing much larger numbers in a similar way. It was also quite interesting to see what the calculation would be.

Thanks for the help everyone, I'll have a read of those links but probably will just forget trying to write the code for dealing with large numbers

Login to post a reply

Server time is: 2024-11-25 03:38:10
Your offset time is: 2024-11-25 03:38:10