Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

I'm trying to use a factor utility but it tells me that number is too large. Is there any utility that can do what factor doing but not tells that number is too large?

share|improve this question
    
How large is the number? –  Ketan Jul 9 at 16:34
    
It is a FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 in decimal, 78 characters in length. –  hiprivet Jul 9 at 16:37
1  
May be it is a system config/capacity issue. Works for me: $ factor 115792089237316195423570985008687907852837564279074904382605163141518161494337 115792089237316195423570985008687907852837564279074904382605163141518161494337: 115792089237316195423570985008687907852837564279074904382605163141518161494337 –  Ketan Jul 9 at 16:40
1  
You can use ruby. Ruby has the ability to handle obscenely long numbers. require 'prime'; puts(0xffffdeadbeef.prime_division.inspect). –  Patrick Jul 9 at 17:02
1  
Do not use prime_division.inspect in ruby. It is extremely slow! factor.pl from Math::Prime::Util is OK, or use Pari/GP's factor function. For instance, try on: 806578020551755900412008880903137528217525975284037923 –  vinc17 Jul 9 at 19:35

2 Answers 2

up vote 4 down vote accepted

Maybe your factor is not built with GMP, so it can not handle number bigger than 2**64-1:

$ factor 18446744073709551616
factor: `18446744073709551616' is too large
$ factor 18446744073709551615
18446744073709551615: 3 5 17 257 641 65537 6700417

Running this command to check if factor built with GMP:

$ ldd /usr/bin/factor 
        linux-vdso.so.1 (0x00007fffda1fe000)
        libgmp.so.10 => /usr/lib64/libgmp.so.10 (0x00007faae00f5000)
        libc.so.6 => /lib64/libc.so.6 (0x00007faadfd46000)
        /lib64/ld-linux-x86-64.so.2 (0x00007faae037c000)

The limit may be higher on some machines (the number has to fit in uintmax_t type), but your number is a 256-bit number, and no common machine supports such a big uintmax_t, if any.

Note that the factor utility can be compiled with GMP support. In that case, there is effectively no limit on the size of the number. It appears that your distribution hasn't activated GMP support (which makes sense since it would add a dependency on an extra library to a core system package for a rarely used feature).

If you have perl, you can try factor.pl program include in Math::Prime::Util module:

$ /home/cuonglm/.cpan/build/Math-Prime-Util-0.31-9c_xq3/bin/factor.pl 115792089237316195423570985008687907852837564279074904382605163141518161494337
115792089237316195423570985008687907852837564279074904382605163141518161494337: 115792089237316195423570985008687907852837564279074904382605163141518161494337
share|improve this answer
4  
By this logic, FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 shouldn't work even on a 64-bit system as that's WAY bigger than 64 bit. (and indeed it doesn't on my system, which is 64-bit) –  Patrick Jul 9 at 17:03
    
Thanks, 'll try it too! –  hiprivet Jul 9 at 17:18
2  
@Patrick: Oh, your factor does not buid with GNU MP, so it can not handle arbitrary-precision numbers. See info factor for more details. –  Gnouc Jul 9 at 19:43
1  
Newer versions of factor in coreutils use 2 uint64_t's, or GMP if chosen when compiled. The maximum it can handle on my 64-bit ubuntu system is 2^127-1, so apparently it wasn't built with GMP. –  Mark Plotnick Jul 9 at 19:46
2  
@richard No: factor supports 64-bit numbers on most 32-bit platforms. –  Gilles Jul 9 at 20:11

You can also use factor from the coreutils. However it needs to be compiled with bignum support. FYI, this is not the case with the binary that comes with some distributions, such as Debian (bug 608832). But you can download the source and recompile it after installing GMP (which is used by default if found).

Another solution is to use Pari/GP (well-known for number theory):

? factor(806578020551755900412008880903137528217525975284037923)
%1 =
[ 238366085426200783161668947 1]

[3383778439410064898661524209 1]

With this number, it takes a few seconds.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.