Factoring contest.

bugzpodder · **Posted:** Thu Feb 23, 2006 11:09 pm

who said anything about making a living off factoring? you'll need to know most current advanced algorithms in order to just attempt this problem. factoring is harder than np hard

md · **Posted:** Fri Feb 24, 2006 5:18 am

The hardest part about this problem: dividing (or multiplying) two numbers that may be up to 212 digits each. Once you got that down all you need is CPU time. Lots and lots of CPU time...

Andy · **Posted:** Fri Feb 24, 2006 8:30 am

30 opeteron years of cpu time

codemage · **Posted:** Fri Feb 24, 2006 10:10 am

Cornflake wrote:

The hardest part about this problem: dividing (or multiplying) two numbers that may be up to 212 digits each.

That's news to anyone who thought the hardest part was fitting the number into an int type with Turing.

md · **Posted:** Fri Feb 24, 2006 5:52 pm

codemage wrote:

Cornflake wrote:

The hardest part about this problem: dividing (or multiplying) two numbers that may be up to 212 digits each.

That's news to anyone who thought the hardest part was fitting the number into an int type with Turing.

You could do it with turing... not with ints... but it's still doable... /me shudders at the thought.

Andy · **Posted:** Fri Feb 24, 2006 6:54 pm

yea that would be uber painful since a turing string can only stolre 255 characters...

md · **Posted:** Fri Feb 24, 2006 7:02 pm

Andy wrote:

yea that would be uber painful since a turing string can only stolre 255 characters...

There is another solution... one that actually does involve ints... but it's rather convoluted and quite challenging to implement.

Andy · **Posted:** Fri Feb 24, 2006 7:11 pm

ints in an array?

md · **Posted:** Fri Feb 24, 2006 8:23 pm

kinda; basically it involves stringing them together. The hard part is what happens when one number rolls over and how you pass that information on to the next.

bugzpodder · **Posted:** Fri Feb 24, 2006 9:42 pm

Cornflake wrote:

The hardest part about this problem: dividing (or multiplying) two numbers that may be up to 212 digits each. Once you got that down all you need is CPU time. Lots and lots of CPU time...

thats trivial... simple paper and pen methods run for O(n^2)... (trivial part) or Fourier transform takes O(n^1.4) time (not so trivial)

for 212 digits, paper and pen is more than enough if you choose ur base intelligently (Base 10 is stupid. base 2^32 is smart)

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members