#16
  1. Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Feb 2005
    Posts
    588
    Rep Power
    64
    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
  2. #17
  3. 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.
  4. #18
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,696
    Rep Power
    480
    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!
  6. #19
  7. 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.
  8. #20
  9. Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Feb 2005
    Posts
    588
    Rep Power
    64
    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
  10. #21
  11. 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.
  12. #22
  13. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,696
    Rep Power
    480
    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!
  14. #23
  15. 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.
  16. #24
  17. Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Feb 2005
    Posts
    588
    Rep Power
    64
    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
  18. #25
  19. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,696
    Rep Power
    480
    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!
  20. #26
  21. 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.
  22. #27
  23. 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
  24. #28
  25. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,696
    Rep Power
    480
    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!
  26. #29
  27. 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.
  28. #30
  29. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,696
    Rep Power
    480
    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.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo