November 9th, 2012, 02:45 PM

Oh yes, C and C++ are limited on the size of integers.
That reminds me, Python has a module decimal
that does calculations on string numerics. C and C++
can use a similar approach.
Real Programmers always confuse Christmas and Halloween because Oct31 == Dec25
November 9th, 2012, 02:49 PM

That sounds interesting.
Can you give an example, like checking if 11 is a prime factor "1111111111" ?
Currently, I'd do that this way:
Code:
s='1'*10
i=int(s)
if i%11==0: print ("YAY")
Thanks.
November 9th, 2012, 02:50 PM

I've got a 64 bit version of python, I suppose. That could make a big difference in run time.
Also, back in post 4 I mentioned the gmp.
Using libgmp c does support large integers.
[code]
Code tags[/code] are essential for python code and Makefiles!
November 9th, 2012, 02:53 PM

Originally Posted by b49P23TIvg
I've got a 64 bit version of python, I suppose. That could make a big difference in run time.
Also, back in post 4 I mentioned the gmp.
Using libgmp c does support large integers.
Okay, that's true. The 3.3.0 I just installed is a 64 bit, but the others (2.6 and 2.7) are probably just 32 bit.
Thanks for the info about libgmp  I may just try that one of these days.
(still waiting for int(s) to finish on my 10^8 long s.
November 9th, 2012, 03:03 PM

Code:
import decimal as dc
s = '1'*10
d = dc.Decimal(s)
if d % dc.Decimal('11') == 0:
print("YAY")
Real Programmers always confuse Christmas and Halloween because Oct31 == Dec25
November 9th, 2012, 03:16 PM

Originally Posted by Dietrich
Code:
import decimal as dc
s = '1'*10
d = dc.Decimal(s)
if d % dc.Decimal('11') == 0:
print("YAY")
Thanks, but the problem with this is that while the (long) integer in Python is without a roof (until you use all the memory), this one isn't. If you instead of '1'*10 did '1'*10**2 it would complain.
November 9th, 2012, 03:19 PM

Yes, I'd use
s='1'*10
i=int(s)
if i%11==0: print ("YAY")
After that I'd replace i by i/11 to reduce the problem size. You haven't gotten to the divisions yet? And you're worried about string to integer conversion time? No no, you showed a couple results in your second post.
[code]
Code tags[/code] are essential for python code and Makefiles!
November 9th, 2012, 03:36 PM

Originally Posted by b49P23TIvg
Yes, I'd use
s='1'*10
i=int(s)
if i%11==0: print ("YAY")
After that I'd replace i by i/11 to reduce the problem size. You haven't gotten to the divisions yet? And you're worried about string to integer conversion time? No no, you showed a couple results in your second post.
Interesting. So what you're saying is that you can do this because they're prime factors?  Very interesting. Thanks!
If I was testing to see if 5 and 10 were factors of 20, and I divided 20 with 5 after testing 5, 10 would no longer be a factor.
November 9th, 2012, 03:36 PM

Try this:
Code:
import decimal as dc
size = 1000
# adjust the precision
dc.getcontext().prec = size
s = '1' * size
d = dc.Decimal(s)
if d % dc.Decimal('11') == 0:
print("YAY")
Real Programmers always confuse Christmas and Halloween because Oct31 == Dec25
November 9th, 2012, 03:37 PM

I doubt that that the decimal module is faster, but it is an alternative. Read the documents! The conversion to internal form takes 4 times longer than does d=int(s)
Code:
import decimal
decimal.getcontext().prec = int(1e6)+1
s = '1'*int(1e6)
d = decimal.Decimal(s)
Great, now that you know all this time some divisions as well.
[code]
Code tags[/code] are essential for python code and Makefiles!
November 9th, 2012, 03:40 PM

Thanks again.
For this project, the factor checking is not the bottleneck, as it goes a lot faster than the int(s) it's waiting on; but thanks for the information.
November 9th, 2012, 03:57 PM

Originally Posted by KINGOLE
Thanks again.
For this project, the factor checking is not the bottleneck, as it goes a lot faster than the int(s) it's waiting on; but thanks for the information.
A side question:
Since this should speed up the factor checking, and since I have created an array with all primes < 100,000, it would make sense to check and divide them with the highest numbers first, to reduce i the most from the beginning.
Is there a way to run a FOR on an array backwards without using RANGE?
forward example:
Code:
for p in pa:
if i%p==0:
i/=p
backward example:
Code:
for p in range (len(pa), 0, 1):
if i%p==0:
i/=p
EDIT: I know that I could've just filled the array with the highest primes first, but I'd still like to know.
Thanks,
Ole
November 9th, 2012, 04:11 PM

for p in reversed(list_of_primes):
>>> help(reversed)
Interesting, please post if you find out that the program runs faster using primes from largest to smallest. I'd bet against only because I'd rather work from low to high by hand.
[code]
Code tags[/code] are essential for python code and Makefiles!
November 9th, 2012, 04:16 PM

Originally Posted by b49P23TIvg
for p in reversed(list_of_primes):
>>> help(reversed)
Interesting, please post if you find out that the program runs faster using primes from largest to smallest. I'd bet against only because I'd rather work from low to high by hand.
Thanks  that was too easy!!!
Again, I don't think speed will be a big issue with the mod/div in this project, as the int(s) is the major bottleneck.
If I was a math genius, I wouldn't even have to do it this way.
November 9th, 2012, 06:29 PM

The division part of your program might be faster using divmod. Then again, you might end up storing a bunch of really long unused quotients. Don't know.
Code:
>>> help(divmod)
Help on builtin function divmod in module __builtin__:
divmod(...)
divmod(x, y) > (quotient, remainder)
Return the tuple ((xx%y)/y, x%y). Invariant: div*y + mod == x.
[code]
Code tags[/code] are essential for python code and Makefiles!