hi there, suppose you have got a 1000,000 digit number held in memory, and you need to represent the number in its smallest possible form, would either prime factorising the number be advisable or converting it into a completely different base, i.e. 60. You would have to use a different character set which would be greater than f (hex). The number will be held within a data structure, and can therefore be manipulated accordingly. Any ideas on this people?
Thank you.
scientific notation is a good choice if there are a lot of zeros and you don't need to be exact. As for converting it to base 60... it's not that hard, and if you use numbers, lowercase, and uppercase letters all as "symbols," you could technically go up to base 62 without too many difficulties...but who the heck is going to want to deal with a base 60 or 62 number? Base 16 is a common one - you could use that, and it would still lob off a sizable number of digits of a number that big. Factoring, and displaying the number like 2^234 * 3^127 * 5^934 could work, but it would take a while and just, in general, be strange. But in what kind of data structure are you holding that? Why do you need a number that big? If you have a number that big, why do you need to display it? How exact does it need to be? Why do you need to display it in "smallest possible form"? By that, I assume that you mean the fewest number of characters. How many characters do you have with which to display it? Is it an int, or might it have decimal places? But, most of all, I reitterate, WHY?!?
The answers to those are important for getting a better solution to the problem.
Away.
The data structure will be a linked list, containing a void ptr to the next node, and an unsigned char representing the data. Therefore, a 1,000,000 digit number should be able to be held in ((32 + 8) * 1,000,000 / 8 / 1024 / 1024) memory using roughly 4.77 mb. If my calculations are correct. I don’t really want to go into too much detail as to its application, I just really wanted to know if it was possible. The list will not be doubly linked to save on memory.
Why? Why use a void pointer? In C I can maybe see a reason for it, but in C++ there is hardly ever a reason to use a void pointer. Wouldn't you just use a node pointer? Why void?Originally posted by pete
The data structure will be a linked list, containing a void ptr to the next node, and an unsigned char representing the data.
Quzah.
Hope is the first step on the road to disappointment.
Actually... why use a linked list? Couldn't you just use an array (albeit a very large one) or several arrays, each of a smaller size, so that you could dynamically allocate it, if needed? like this?
Code:unsigned char array1[10000] unsigned char array2[10000] unsigned char array3[10000] unsigned char array4[10000] unsigned char array5[10000] unsigned char array6[10000] unsigned char array7[10000] unsigned char array8[10000] unsigned char array9[10000] unsigned char array10[10000]
Away.
Without knowing why, you're not going to get much help.
And factoring arbitrary numbers of 1 million digits??? Such a thing isn't possible for every computer on earth within the lifetime of the universe. Encryption as we know it would be impossible if it were.
I guess the best thing, not knowing anything about your needs, would be to use base 100, because it's very easy to convert from base 10. Either that or packed BCD, which is just as space saving.
I agree about not using a linked list; you should be able to get 1 MB of memory easily enough with a call to new(), malloc(), or an OS-specific allocation. If you use base 100, you need only 500 KB of memory because each digit is 1/2 of a byte.
Last edited by Cat; 06-12-2003 at 07:48 PM.
blackrat364, yeah you could have an array of ptrs and allocate memory accordingly. They would be faster as well since they are held in contiguous memory blocks. The only downside to this method is that you would have to check every time you are going initialise an element of the array, that it is not actually the end of the array. However, I don’t really think it is much of a processing overhead.
So, is there a general formula which you can apply which would roughly tell you how many new digits could represent the number? So if I was using base 100, and the number was 10^1,000,000 to calculate the number of new representations would it be
10^1,000,000 / 100, i.e. 10,000?
The number of digits for number n when converted to base 100 would be 100log(n) + 1.
Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah
You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie
By this, he means the base-100 log of N.Originally posted by XSquared
The number of digits for number n when converted to base 100 would be 100log(n) + 1.
The way to figure out the number of new digits, once you know the number of base-10 digits, is to divide by the log of the base. E.g. 156,432 takes 6 base-10 digits, but would only take 2 base-1000 digits (6/log(1000)).
It's easy to figure out base-100 by inspection, because each digit of a base-100 number represents exactly two digits in base 10 (digits 00 through 99). It's thus very easy to convert between them.
Packed BCD is even easier, though.
Last edited by Cat; 06-12-2003 at 10:35 PM.
Should be possible. You sart by checking if(number%2==number/2), and if it is, you know you can divide by 2, so that is the first prime factor, so then you take the new number (original divided by factor) and repeat the process with that. The only factors you need to check are the primes...and unless your 1 million digit number is prime (which would suck), you shouldn't run into too many problems. I think it could be done.Originally posted by Cat
And factoring arbitrary numbers of 1 million digits??? Such a thing isn't possible for every computer on earth within the lifetime of the universe. Encryption as we know it would be impossible if it were.
And if this post didn't make sense, give me a break. It's 1:30 and the past two nights, I've gone to bed at 3:00 and 3:00...so I'm running without much sleep.
Away.
>> ...so I'm running without much sleep.
Definitely know the feeling there.
While the process of getting the prime factorization is possible, it is an extremely computationally intensive task (and the bext known algorithm for determining precisely if a number is prime is to check all primes up to the square root of the number).
For public key cryptography, 1024 and 2048 bit (not digit) primes are considered secure (and they are often pseudoprimes... that have certain statistical properties of primes, because it would be infeasible to check if they really were primes - see the Miller-Rabin test, et al).
A 1,000,000 digit number is roughly equivalent to 3.32 million bits (if I remember log2 of 10 correctly). So, it'd take a very long time to factor.
(Also note that symmetric encryption algorithms are quite independent of prime numbers.)
The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.
Theoretically? Yes, it can be done. But it would take far too long.Originally posted by blackrat364
Should be possible. You sart by checking if(number%2==number/2), and if it is, you know you can divide by 2, so that is the first prime factor, so then you take the new number (original divided by factor) and repeat the process with that. The only factors you need to check are the primes...and unless your 1 million digit number is prime (which would suck), you shouldn't run into too many problems. I think it could be done.
And if this post didn't make sense, give me a break. It's 1:30 and the past two nights, I've gone to bed at 3:00 and 3:00...so I'm running without much sleep.
Public Key Cryptography could be broken if you could factor a number that is 1024 bits (as far as I know, it hasn't been done, even by large distributed computing), which is 308 decimal digits.
The algorithm you propose is acceptable (you couldn't use native data types, of course), but it would just take too long. There are a LOT of primes, and we don't even KNOW all of the primes less than 10^1,000,000. That's a REALLY big number.
Hi all thank you so much for all your replies. They are all very helpful. I have just got another question. If you have a long double will that variable be able to store every possible combination of numbers between 0 >= && <= 1*10^4932. I mean all unsigned as well, no floating points. So if I did, long double a = powl(10,4932) – 1;
Would the variable a now contain 99999999999999999…..99999 and so on until 4931 digits (I think). I tried to see if it did store every combination with a very simple program:
However, I just kept getting the same output. I would really appreciate any help on this,Code:#include <math.h> #include <iostream.h> int main(void) { long double a = powl(10, 4932), b = 1; for(int i=0; i < 25; i++) cout << (a -= b) << "\n"; return 0; }
Thanks, Pete.
You mean every possible integer? No. It's easy to see it can't -- there are only 2^64 unique 64-bit numbers. Even if you have access to a 128-bit floating point type, 2^128 < 10^4932.Originally posted by Pete
Hi all thank you so much for all your replies. They are all very helpful. I have just got another question. If you have a long double will that variable be able to store every possible combination of numbers between 0 >= && <= 1*10^4932.
To uniquely store every integer up to 10^4932 would take a minimum of 16,384 bits.
Last edited by Cat; 06-13-2003 at 10:33 AM.
