10 million digits

[b][red]This message was edited by DarQ at 2004-2-4 11:20:34[/red][/b][hr]
Hi

i just started a week ago coding C, and i love it already! especially the fact that what i code in winNT, can be compiled on my linux box without a problem :D But i have a question now to which i haven't found an answer yet.

today i made a thing that finds prime numbers. As the numbers grow larger, the proccess takes longer, but there is a trick for that ;)
The problem now is, that i want to exceed the storage capacity of unsigned longs.. use numbers of about 10 MILLION digits.

now, 10 million might be a bit too much for now, but an unsigned long has certainly not enough digits.

can anyone kick my in the right direction?

greets!
[size=5][italic][blue]Dar[RED]Q[/RED][/blue][/italic][/size]
NEW url--> http://mark.space.servehttp.com


Comments

  • The solution is NOT easy. The primitive data types are there to be used, and they have sizes that are supposed to be "reasonable". But sometimes you do have to go over the limit. A solution would be to create a struct that contains two unsigned longs in it. Then you modify your algorithm that finds prime numbers to work with this struct. Everything needs to be modified because no c runtime functions will be able to just work with your new data type.

    [code]
    struct LARGE_NUM{
    unsigned long num1;
    unsigned long num2;
    };

    [/code]

    num1 could be the primary storage area, and num2 is where the overflow bytes (the digits that don't fit into num1) go. This kind of stuff requires some knowledge of how the computer stores these data types. This can be platform specific...

  • : [b][red]This message was edited by DarQ at 2004-2-4 11:20:34[/red][/b][hr]
    : Hi
    :
    : i just started a week ago coding C, and i love it already! especially the fact that what i code in winNT, can be compiled on my linux box without a problem :D But i have a question now to which i haven't found an answer yet.
    :
    : today i made a thing that finds prime numbers. As the numbers grow larger, the proccess takes longer, but there is a trick for that ;)
    : The problem now is, that i want to exceed the storage capacity of unsigned longs.. use numbers of about 10 MILLION digits.
    :
    : now, 10 million might be a bit too much for now, but an unsigned long has certainly not enough digits.
    :
    : can anyone kick my in the right direction?
    :
    : greets!
    : [size=5][italic][blue]Dar[RED]Q[/RED][/blue][/italic][/size]
    : NEW url--> http://mark.space.servehttp.com
    :
    :
    :

    [green] 10 million digits in what? Decimal, hexidecimal, octal, binary?
    If decimal or any other numbering system said above is used then it's going to require [b][red]ALOT[/red][/b] of memory. Probably 10 to the what ever power(I'm not even going to figure it out) decimal converted into a binary equivalent of the greatest value you will ever need. On top of that, your variable usage would be astounding to even type by hand, so that would have to be automated also since the most a variable that I know of can hold is 80bit numbers on a PC. That's probably why those super puter's that analyze astronomical equations are so expensive because you need it to handle big numbers and be fast at the same time.


  • : [code]
    : struct LARGE_NUM{
    : unsigned long num1;
    : unsigned long num2;
    : };
    :
    : [/code]

    i guess dividing such numbers would work like asm with 2 bytes or more??

    btw: i've seen something about unsigned long long's. how big are those?
    [size=5][italic][blue]Dar[RED]Q[/RED][/blue][/italic][/size]
    NEW url--> http://mark.space.servehttp.com

  • [red]
    : btw: i've seen something about unsigned long long's. how big are those?
    [/red]

    64bit

    Like I said before the biggest variable type I know of is 80bit or a tbyte also a real 10 which is of course a 10byte number, but I don't remember how it would be declared in C since I have never messed with numbers that big in c or anything else in that matter.
  • : : [b][red]This message was edited by DarQ at 2004-2-4 11:20:34[/red][/b][hr]
    : : Hi
    : :
    : : i just started a week ago coding C, and i love it already! especially the fact that what i code in winNT, can be compiled on my linux box without a problem :D But i have a question now to which i haven't found an answer yet.
    : :
    : : today i made a thing that finds prime numbers. As the numbers grow larger, the proccess takes longer, but there is a trick for that ;)
    : : The problem now is, that i want to exceed the storage capacity of unsigned longs.. use numbers of about 10 MILLION digits.
    : :
    : : now, 10 million might be a bit too much for now, but an unsigned long has certainly not enough digits.
    : :
    : : can anyone kick my in the right direction?
    : :
    : : greets!
    : : [size=5][italic][blue]Dar[RED]Q[/RED][/blue][/italic][/size]
    : : NEW url--> http://mark.space.servehttp.com
    : :
    : :
    : :
    :
    : [green] 10 million digits in what? Decimal, hexidecimal, octal, binary?
    : If decimal or any other numbering system said above is used then it's going to require [b][red]ALOT[/red][/b] of memory. Probably 10 to the what ever power(I'm not even going to figure it out) decimal converted into a binary equivalent of the greatest value you will ever need. On top of that, your variable usage would be astounding to even type by hand, so that would have to be automated also since the most a variable that I know of can hold is 80bit numbers on a PC. That's probably why those super puter's that analyze astronomical equations are so expensive because you need it to handle big numbers and be fast at the same time.
    :
    :


    ===========================================================


    hey...why dont u try changing a file called "limits.h" , which has the min & max values of almost all the things ( with values ) , and i have seen datatypes like "long long".

  • :
    : hey...why dont u try changing a file called "limits.h" , which has the min & max values of almost all the things ( with values ) , and i have seen datatypes like "long long".
    :
    :

    [blue]Yes, Windows OS has a "long long" data type, which is a 64-bit number. It's twice the size of a long, but doesn't even come close to holding 10,000,000 digits. There is simply no way to do that on a PC using native data types and current archetecture. Maybe, just maybe, if you go to NASA they can help you.[/blue]
  • i see..

    im aware that no datatype can hold plenty digits. but if you can do 16 bits divisions on an 8 bits cpu (asm), then with C it should work as well, i hope ;)

    i will try to figure it out by using quite a few longs.
    :
    : [blue]Yes, Windows OS has a "long long" data type, which is a 64-bit number. It's twice the size of a long, but doesn't even come close to holding 10,000,000 digits. There is simply no way to do that on a PC using native data types and current archetecture. Maybe, just maybe, if you go to NASA they can help you.[/blue]
    :

    [size=5][italic][blue]Dar[RED]Q[/RED][/blue][/italic][/size]
    NEW url--> http://mark.space.servehttp.com

  • : [red]
    : : btw: i've seen something about unsigned long long's. how big are those?
    : [/red]
    :
    : 64bit
    :
    : Like I said before the biggest variable type I know of is 80bit or a tbyte also a real 10 which is of course a 10byte number, but I don't remember how it would be declared in C since I have never messed with numbers that big in c or anything else in that matter.
    :

    [green]
    While using a Borland compiler the correct type for an 80bit variable is a long double. 80bits is quite a large variable, its assigned value can be anywhere from 3.4 x 10-4932 to 1.1 x 10+4932.
    [/green]
    [hr]
    [blue][size=4]JBaker[/size][/blue]

  • : : [red]
    : : : btw: i've seen something about unsigned long long's. how big are those?
    : : [/red]
    : :
    : : 64bit
    : :
    : : Like I said before the biggest variable type I know of is 80bit or a tbyte also a real 10 which is of course a 10byte number, but I don't remember how it would be declared in C since I have never messed with numbers that big in c or anything else in that matter.
    : :
    :
    : [green]
    : While using a Borland compiler the correct type for an 80bit variable is a long double. 80bits is quite a large variable, its assigned value can be anywhere from 3.4 x 10-4932 to 1.1 x 10+4932.
    : [/green]
    : [hr]
    : [blue][size=4]JBaker[/size][/blue]
    :
    :
    [blue]So, by that logic, say, value of 0.728672933993887857487376E+4930 will have all the 4930 digits as a significant ones? I doubt that. Mantissa is still limited to some 71 bit or so... and it is not even close to 1000 digits even...[/blue]
  • An avenue that I use when playing with large numbers is to work the digits into strings. Unfortunately, this entails writing your own math routines for the strings, and there is a great loss in memory usage, but the string length becomes the limit of the number of digits. A simple example would be to take the number 12345678901234567891123456789212345678931234567894 and multiply it by 3. This would give the math routines a bit of a challenge but all you really need to do is assign the above number to a string and then write your own routine which does the math based on each digit. For the above your routine will extract the first digit on the right, convert it to its numeric value (character 4 - 48 becomes numeral 4) and then multiply it by the 3 using normal math procedures. Capture any carry and place the converted "ones" result into the first place on the right of a second string (remember to add 48 to the new numeral before placing it in your second string). Work your way left one character at a time and you get the same result as if you were able to do direct math. Granted there is an awful waste in memory and conversion, but it is a solution.

    Take Care,
    Ed Hall

  • : [blue]So, by that logic, say, value of 0.728672933993887857487376E+4930 will have all the 4930 digits as a significant ones? I doubt that. Mantissa is still limited to some 71 bit or so... and it is not even close to 1000 digits even...[/blue]
    :

    [blue]
    I was answering shaolin007's comment;
    [/blue]
    [green]"I don't remember how it would be declared in C..."[/green]
    [blue]
    Meaning an 80bit variable. I think it was pretty clear that I was responding to his/her comment and not DarQ. I did not think my answer was going to close the thread or get DarQ any closer to solving his/her problem. I was only helping where I could.

    I was also pretty clear about using the borland compiler and the documentation is all I have to go by (I've never used variable that big before). So if your more knowledgeable about this compiler and the included documentation then the entire Borland team that put it together then I appologies to you but as you said so well [/blue][red]"...I doubt that..."[/red][blue]. My comment for shaolin007 was correct, deal with it.

    So, if shaolin007 wanted to initialize an 80bit variable now he/she knows how to do it.

    In closing, try to keep in mind that this message board is all about helping people with problems that relate to C/C++ programming. This is not a flaming board or a one-up you type of situation. Anyone who has been programming for longer then a week knows that there is almost always more then one way to get the job done. The end result is the most important thing to your employer.[/blue]
    [hr]
    [blue][size=4]JBaker[/size][/blue]

  • After having done some more playing it seems that 10 million is a bit out of my reach using the string method I mentioned. I was only able (with my setup) to create a string up to a little over 2 million digits long before I encountered a stack fault. Oh well, back to my play. . .

    BTW, 16609 is the maximum power of 2 that can fit in 5000 digits. . .:-)

    Take Care,
    Ed Hall

  • just say __int64.
    to make it portable on linux just say
    #define long long __int64

    now declare the variable as

    long long

  • : just say __int64.
    : to make it portable on linux just say
    : #define long long __int64
    :
    : now declare the variable as
    :
    : long long
    :
    :
    Thanks for the reply Pratham,

    When I try this I get messages such as "long long long is too long" for the declaration statement. I had tried the long long approach without the __int64 part. I suspect my difficultiy is stemming from my individual machine perhaps (although it could be my code environment) because if I add code elsewhere the string size capability decreases. Also if I add a second string it shortens the first's capability. Is this possibly some sort of small, medium, large issue? I kind of thought that was not an issue with 32bits, but maybe I'm mixing Windows and Console thinking. . .

    Take Care,
    Ed Hall

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories