-
We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.
Need a program to factor large (50 digit) numbers
Page 2 - Seeking answers? Join the AnandTech community: where nearly half-a-million members share solutions and discuss the latest tech.
Oh btw I found this site:
http://www.alpertron.com.ar/ECM.HTM
which seems to use your home computer for factor the number using some method I've never seen before...can anyone explain the Elliptic Curve Method?
http://www.alpertron.com.ar/ECM.HTM
which seems to use your home computer for factor the number using some method I've never seen before...can anyone explain the Elliptic Curve Method?
mugs
Lifer
I was just going to suggest your edit. 😉 First google search result gave me a website with the ~450 million prime numbers between 0 and 10 billion. I'm thinking you might need some bigger numbers than that though. But maybe not. If your prof got that number by multiplying a bunch of prime numbers together, he probably didn't use any primes higher than 10 billion. 🙂
drinkmorejava
Diamond Member
wow, um 212 digits, how do you get 50 out of that. Sorry to dissapoint you, but I'm not going to waste time making the program handle a number than big. A normal double value only goes to 2^64 (-1 i think) which is like 18446744073709551615. Def not 212 digits.
CycloWizard
Lifer
Just write down that number and one. If it's prime (my guess), then you get the extra credit with no work. If not, oh well - you weren't getting it anyway.
sciencewhiz
Diamond Member
Your teacher may give you extra credit. I'll give you $10,000.
drinkmorejava
Diamond Member
Ok, I wrote a java factoring program, it's amazingly inefficient but w/e. If you want to mess around with it be my guest, but there's no way it'll do a number that long
you can find the source at www.randomdeviance.com/java/Factor
there's a Keyboard class package (cs1) in there that you'll need to compile, otherwise I threw the compiled classes in there too.
you can find the source at www.randomdeviance.com/java/Factor
there's a Keyboard class package (cs1) in there that you'll need to compile, otherwise I threw the compiled classes in there too.
drinkmorejava
Diamond Member
cool, I might do that later and add a dynamic base case and incrementor for the loop...and then set it up for a week on an A XP 2800.
Kyteland
Diamond Member
I have a c++ program chugging away seeing if it's divisible by any of the first 15 million primes. It'll take about an hour to run.
Your only hope of factoring this is that your teacher multiplied a bunch of <9 digit primes together and not two large prime numbers.
Edit: I'm through the first 5 million and no prime factors fo far.
Edit: Up to 13 million. I would give up and say it isn't going to happen.
Your only hope of factoring this is that your teacher multiplied a bunch of <9 digit primes together and not two large prime numbers.
Edit: I'm through the first 5 million and no prime factors fo far.
Edit: Up to 13 million. I would give up and say it isn't going to happen.
drinkmorejava: is there a reason you stored the factors in a string rather than an array? I always figure that it made sense to leave numbers as ints/doubles so you can go back and use them as such should you choose to do so later and can print them just as easily as printing a string. All in all, pretty much exactly what I would have written (I've given up trying to find it) but assuming I had the time, I would have put the first x number of primes into an array and just modded the number by them.
Off topic question: for the last part of the program: the else {i++}, wouldn't it be faster to delete that and change the for loop to read for (int i=2; i<=(newnumber/3); i=i+2)? You essentially absorb the else command when you increment the loop...
Final question: what do you mean by adding a dynamic base case? I a. don't know what you mean and b. can't see anything to really gain unless it somehow involves multithreading...
Off topic question: for the last part of the program: the else {i++}, wouldn't it be faster to delete that and change the for loop to read for (int i=2; i<=(newnumber/3); i=i+2)? You essentially absorb the else command when you increment the loop...
Final question: what do you mean by adding a dynamic base case? I a. don't know what you mean and b. can't see anything to really gain unless it somehow involves multithreading...
ActuaryTm
Diamond Member
drinkmorejava
Diamond Member
Yes, an array would have been better if I wanted to go back later; however, I'm not sure what for. The only thing I'm coming up with is maybe to sort it, but if we're talking about lots of numbers, there's no reason to add something with an O(n^2) inefficiency. Yes, an array with the first x primes would be more efficient, I even have a program I made a while back that will compute them...or one could just d/l them...of course, if I actually stored them, that's several megabytes worth of stuff in the source that I wouldn't feel like uploading.
LOL, I didn't even realize that I was doing two i++ in there, now that I think about it logically, it actually makes sense to increment by two too, but because I don't have an i++ in the if, it kind of messes it up. Then again, if I really wanted I could just make the loop a massive recursive function; point being, never ask me to program anything for you...which you didn't.
by a dynamic base case (base case is the term used in recursive functions for what will cause it to be satisfied)* I mean it would terminate the loop iteration sooner depending on what number it's checking, but if you use a list of primes anyway it wouldn't do anything. Like if we have the number 100, I could check every value up to 33, but this condition of this would be satisfied by 3, same with checking ever number up to 50 which would be satisfied by 2. In this case it would stop at 2, divide the number and repeat using 50 as the new value, but for something that is a prime number, it would make no sense to keep going that high when we'd be sure there would be no solution.
*ie: if you had
int i=0;
increase(int x)
{
if x>0
{i++; increase(x);}
}
it would loop around forever because the base case being x>0, will never not be true until it got to (x^31)-1 whence it would crash due to the int being to large; or to really elaborate, it would prob turn into a negative number, weird how that seems to happen, in which case the method would do nothing
AND THIS PEOPLE, IS WHY WE NEED A SEPARATE PROGRAMMING GATEGORY
LOL, I didn't even realize that I was doing two i++ in there, now that I think about it logically, it actually makes sense to increment by two too, but because I don't have an i++ in the if, it kind of messes it up. Then again, if I really wanted I could just make the loop a massive recursive function; point being, never ask me to program anything for you...which you didn't.
by a dynamic base case (base case is the term used in recursive functions for what will cause it to be satisfied)* I mean it would terminate the loop iteration sooner depending on what number it's checking, but if you use a list of primes anyway it wouldn't do anything. Like if we have the number 100, I could check every value up to 33, but this condition of this would be satisfied by 3, same with checking ever number up to 50 which would be satisfied by 2. In this case it would stop at 2, divide the number and repeat using 50 as the new value, but for something that is a prime number, it would make no sense to keep going that high when we'd be sure there would be no solution.
*ie: if you had
int i=0;
increase(int x)
{
if x>0
{i++; increase(x);}
}
it would loop around forever because the base case being x>0, will never not be true until it got to (x^31)-1 whence it would crash due to the int being to large; or to really elaborate, it would prob turn into a negative number, weird how that seems to happen, in which case the method would do nothing
AND THIS PEOPLE, IS WHY WE NEED A SEPARATE PROGRAMMING GATEGORY
drinkmorejava
Diamond Member
lol, what is that, it looks like a debug dump or something.
TRENDING THREADS
-
Discussion Zen 5 Speculation (EPYC Turin and Strix Point/Granite Ridge - Ryzen 9000)- Started by DisEnchantment
- Replies: 25K
-
Discussion Intel Meteor, Arrow, Lunar & Panther Lakes + WCL Discussion Threads
- Started by Tigerick
- Replies: 25K
-
Discussion Intel current and future Lakes & Rapids thread- Started by TheF34RChannel
- Replies: 24K
-
-
