Can someone factor 2^61-1 for me?

[beer]

Actually, I looked into this further. I played with the MATLAB memory settings and started factoring 2^55. I set it's affinity to run only on CPU0 of my hyperthreaded machine, so I can still use Windows without a problem. Basically, memory usage seems to spike to 400MBish as it handles the vector operations, but matlab still reports 'busy' even though it is utilizing <10% of the CPU. That, to me, confirms that factoring a large number on an x86 box is limited by memory bandwidth, and not functional units. If functional units were the limiting factor, matlab would be eating up the CPU like mad, but since it's hovering around low values, it's just waiting on Windows to page in the correct amounts of memory. This is on a machine with 1 GB of RAM, and a datatype of 1:n:2^55 is, umm, 2^55*2^8 bytes long, when defaulted to 'double' as matlab does. That's a *LOT* of virtual memory to be moving about. And x86 has sh!tty memory bandwidth anyways.

 

[RaynorWolfcastle]

I haven't actually looked at the matlab code but it couldn't possibly do it using a double because there aren't enough mantissa bits to accurately represent 2^61-1 with enough precision (IIRC the precision of a double is somewhere between 16 & 17 decimal places) since 2^61-1 is 18 digits long. With that said, matlab definitely has integer datatypes (though the default is double-precision float, as you said). Either way, neither of these datatypes are acceptable to factor a number like 2^61-1, so they probably use some trick where they split the number into several parts and fool around with it. Obviously, to get something to work with an arbitrarily long number is a huge mess and takes a crapload of computation to work around register-length limitations.

In practice, to find prime numbers they use an FFT-based algorithm that's shown on the Mersenne Primes webpage.

 

[beer]

Originally posted by: RaynorWolfcastle
I haven't actually looked at the matlab code but it couldn't possibly do it using a double because there aren't enough mantissa bits to accurately represent 2^61-1 with enough precision (IIRC the precision of a double is somewhere between 16 & 17 decimal places) since 2^61-1 is 18 digits long. With that said, matlab definitely has integer datatypes (though the default is double-precision float, as you said). Either way, neither of these datatypes are acceptable to factor a number like 2^61-1, so they probably use some trick where they split the number into several parts and fool around with it. Obviously, to get something to work with an arbitrarily long number is a huge mess and takes a crapload of computation to work around register-length limitations.

In practice, to find prime numbers they use an FFT-based algorithm that's shown on the Mersenne Primes webpage.

Good point about the mantissa bits. Still, I stand behind my belief that it's primarily a memory bandwidth issue, not an arithmatic performance issue. If what you say is right, and I assume it is, and they're fiddling with arbitrary data types, you're executing a LOT of microsubroutines and doing a LOT of loads/stores and that will kill any x86 system.