Thread: String to Int conversion speed

1. 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.
2. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Location
Texas
Posts
24
Rep Power
0
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.
3. 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.
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Location
Texas
Posts
24
Rep Power
0
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.
5. Code:
```import decimal as dc

s = '1'*10
d = dc.Decimal(s)
if d % dc.Decimal('11') == 0:
print("YAY")```
6. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Location
Texas
Posts
24
Rep Power
0
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.
7. 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.
8. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Location
Texas
Posts
24
Rep Power
0
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.
9. Try this:
Code:
```import decimal as dc

size = 1000
dc.getcontext().prec = size

s = '1' * size
d = dc.Decimal(s)
if d % dc.Decimal('11') == 0:
print("YAY")```
10. 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.
11. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Location
Texas
Posts
24
Rep Power
0
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.
12. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Location
Texas
Posts
24
Rep Power
0
Originally Posted by KING-OLE
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
13. 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.
14. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Location
Texas
Posts
24
Rep Power
0
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.
15. 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 built-in function divmod in module __builtin__:

divmod(...)
divmod(x, y) -> (quotient, remainder)

Return the tuple ((x-x%y)/y, x%y).  Invariant: div*y + mod == x.```