Thread Subject: How to expand the bits of matlab's fuction like this-factor

Now,I can only factor() a number that not exceed 2^32
 factor(2^33)
??? Error using ==> factor at 25
The maximum value of n allowed is 2^32.

Though I can use maple and mathematica ,but it's not interesting.
So...

"ma " <underground@live.cn> wrote in message <h9fhhl$ot6$1@fred.mathworks.com>...
> Now,I can only factor() a number that not exceed 2^32
> factor(2^33)
> ??? Error using ==> factor at 25
> The maximum value of n allowed is 2^32.
>
> Though I can use maple and mathematica ,but it's not interesting.
> So...
I am not sure where the limitation is (line 26-28). Edit factor, remove the check and save it as factorme.m:

factorme(2^33*3*5*13)
ans = 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5 13

Of course you need 64 bit. I do not know why it is hard limited to 2^32.

"ma " <underground@live.cn> wrote in message <h9fhhl$ot6$1@fred.mathworks.com>...
> Now,I can only factor() a number that not exceed 2^32
> factor(2^33)
> ??? Error using ==> factor at 25
> The maximum value of n allowed is 2^32.
>
> Though I can use maple and mathematica ,but it's not interesting.
> So...

Part of the problem is that factor arises from an
earlier version of MATLAB, when it was limited for
memory and speed reasons. factor uses a trial
divide strategy, dividing the number (n) in
question by all the primes below sqrt(n). They
chose to limit factor then to 2^32, since it was
fast and efficient to generate the primes up to
2^16, and then do a trial divide for each such
prime.

Over the years, cpus and memory have grown,
so that factor might arguably be pushed up to
perhaps 2^44 or so, before things bog down
too much. This would require generating the
primes up to 2^22. Even on my now older CPU,
this takes only a relatively short time.

tic,p = primes(2^21);toc,size(p)
Elapsed time is 0.400090 seconds.
ans =
           1 155611

tic,p = primes(2^22);toc,size(p)
Elapsed time is 0.814761 seconds.
ans =
           1 295947

So it might be argued that factor could have
been bumped up a bit with each release. But that
would have been silly.

You can use my own vpi tools to factor somewhat
larger numbers, although I've not (yet) implemented
anything fancy like a quadratic sieve. But the version
of factor in vpi can factor even most 20 digit numbers
in a reasonable time. Again, on my admittedly old
CPU:

tic,f = factor(vpi(2)^33);toc,f
Elapsed time is 0.072250 seconds.
f =
 
Columns 1 through 20
   2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 
Columns 21 through 33
   2 2 2 2 2 2 2 2 2 2 2 2 2


% 20 decimal digits
tic,f = factor(vpi('48818158715554445653'));toc,f
Elapsed time is 2.639966 seconds.
f =
        41 409 7699 97159 3891857

% 25 decimal digits
tic,f = factor(vpi('4881815871555444565345654'));toc,f
Elapsed time is 7.326808 seconds.
f =
        2 13 187762148905978637128679

% 30 decimal digits
tic,f = factor(vpi('488181587155544456534565468749'));toc,f
Elapsed time is 10.423874 seconds.
f =
   488181587155544456534565468749

Oops. it turns out that 488181587155544456534565468749
is a prime number.

>> isprime(vpi('488181587155544456534565468749'))
ans =
     1

So try adding 2 to that number.

tic,f = factor(vpi('488181587155544456534565468751'));toc,f
Elapsed time is 10.500559 seconds.
f =
   488181587155544456534565468751

BLAST! A random twin prime. :) Try again.

tic,f = factor(vpi('488181587155544456534565468747'));toc,f
Elapsed time is 419.496728 seconds.
f =
   3 3 3 3 11 97441 5622920699574668592337

So this one took a bit more work, even using a
better scheme than does the base factor. But it
was able to factor an arbitrary number with 30
decimal digits, far better than the built-in factor.

The fact is, factoring large numbers is hard work.

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message
news:h9fnf2$jv0$1@fred.mathworks.com...
> "ma " <underground@live.cn> wrote in message
> <h9fhhl$ot6$1@fred.mathworks.com>...
>> Now,I can only factor() a number that not exceed 2^32
>> factor(2^33)
>> ??? Error using ==> factor at 25
>> The maximum value of n allowed is 2^32.
>>
>> Though I can use maple and mathematica ,but it's not interesting.
>> So...
>
> Part of the problem is that factor arises from an
> earlier version of MATLAB, when it was limited for
> memory and speed reasons. factor uses a trial
> divide strategy, dividing the number (n) in
> question by all the primes below sqrt(n). They
> chose to limit factor then to 2^32, since it was
> fast and efficient to generate the primes up to
> 2^16, and then do a trial divide for each such
> prime.
>
> Over the years, cpus and memory have grown,
> so that factor might arguably be pushed up to
> perhaps 2^44 or so, before things bog down
> too much. This would require generating the
> primes up to 2^22. Even on my now older CPU,
> this takes only a relatively short time.

Even were we to increase the limit in the FACTOR function, it should (and
probably would) error if the number was greater than 2^53:

x = 2^53;
y = x+1;
areTheyEqual = (x == y)

for the reasons described here (that I know John knows but others may not):

http://www.mathworks.com/company/newsletters/news_notes/pdf/Fall96Cleve.pdf

So if you're looking to factor really large numbers, you should use
something like Symbolic Math Toolbox or John's VPI object.

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ

> Even were we to increase the limit in the FACTOR function, it should (and
> probably would) error if the number was greater than 2^53:
>
> x = 2^53;
> y = x+1;
> areTheyEqual = (x == y)
>
> for the reasons described here (that I know John knows but others may not):
>
> http://www.mathworks.com/company/newsletters/news_notes/pdf/Fall96Cleve.pdf
>
> So if you're looking to factor really large numbers, you should use
> something like Symbolic Math Toolbox or John's VPI object.
>
But still: what is the reason not to increase it to 2^53, since it seems to work fine?