30-liner: swift speedy solution for End Zeros by przemyslaw.daniel - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

30-liner: swift solution in Speedy category for End Zeros by przemyslaw.daniel

def div_10(n):
    ''' fast division by 10'''

    q = (n >> 1) + (n >> 2)
    q = q + (q >> 4)
    q = q + (q >> 8)
    q = q + (q >> 16)
    q = q >> 3
    r = n - (q << 3) - (q << 1)
    return q + ((r + 6) >> 4)


def mul_10(n):
    ''' fast multiplication by 10 '''

    return (n << 3) + (n << 1)


def end_zeros(n):
    ''' count trailing zeros '''
    
    if not n:
        return 1

    out, t = 0, div_10(n)
    while mul_10(t) == n:
        n, t = t, div_10(t)
        out += 1

    return out

March 2, 2020

Comments:

qi.co on Sept. 29, 2020, 6:21 p.m.
Can you explain why `fast division by 10` is correct?

przemyslaw.daniel on Sept. 30, 2020, 5:13 a.m.
you can find description for example <a href="https://hackaday.com/2020/06/12/binary-math-tricks-shifting-to-divide-by-ten-aint-easy/">here</a>

CDG.Axel on Dec. 2, 2021, 6:50 p.m.
Sad that bitwise operation in python isn't fast ( <pre class='brush: python'>from time import time n, st_time = 10000000, time() for i in range(n): x = i * 10 print(f'{n,} iterations, {time() - st_time:.3f} seconds') --> 10,000,000 iterations, 0.319 seconds same for x = (i << 3) + (i << 1) --> 10,000,000 iterations, 0.848 seconds </pre>

przemyslaw.daniel on Dec. 3, 2021, 8:37 a.m.
right, I can see similar results on my machine <pre class='brush: python'>python3 -m timeit '[x*10 for x in range(10000000)]' 1 loop, best of 5: 1.19 sec per loop python3 -m timeit '[(x<<3)+(x<<1) for x in range(10000000)]' 1 loop, best of 5: 2.2 sec per loop </pre> I have to try to create an executable with something like py2exe to see if this is also visible in the standalone application

CDG.Axel on Dec. 3, 2021, 10:42 a.m.
I tried to use bitwise for pattern recognition task (<a href="https://py.checkio.org/mission/matrix-pattern/publications/CDG.Axel/python-3/binary-hardcore-aka-zjoin/">click</a>). Matching pattern with 'image & mask == pattern' faster than cycle by matrix, but matrix to binary transformation nullify all attempts to make a fast code. Even this transformation is too slow :( As like as two cycles <pre class='brush: python'>matrix = [[1, 2, 0], [4, 5, 6]] binary = 0 for el in iter(sum(matrix, [])): binary = binary << 4 | el print(f'{binary:024b}') >> 000100100000010001010110 </pre>

StefanPochmann on March 25, 2024, 5:58 p.m.
Yeah, and the speed ratio is even bigger if you reduce the work other than the operation, and it's even far bigger for division: ``` 0.388 seconds 'for i in r: i * 10' 1.163 seconds 'for i in r: (i << 3) + (i << 1)' 0.464 seconds 'for i in r: i // 10' 5.441 seconds 'for i in r:\n q = (n >> 1) + (n >> 2... ``` That should be expected, as most of the time is spent on Python interpretation, not on the actual calculations, and the "fast" solutions do a lot more operations. But they're also slower for larger values, like dividing/multiplying `n = 3 ** 1000000` by 10, where the time is almost all spent by the calculation: ``` 0.67 ms n // 10 1.57 ms div10(n) 0.07 ms n * 10 0.17 ms mul10(n) ``` So I think this really doesn't belong in "Speedy" :-P Benchmark 1 (<a href="https://ato.pxeger.com/run?1=bVLBasMwDIUd_QE762Z7S9NkCaWEtj9SyuhSZzM0TqI6sDH2Jbv0sn3Uvmay3ZRAY7AtPT09CaHv3_bDvjXmfP7pbTVb_t3dV9jUYHWtQNdtg9bb7IpqO-CoWrW3jJ2U7VtYA-ecGfrT5DlJ_GVILgWPSuDevCphpGSOpt5VKXyeZKxqEMrmQPUMbBnQ4Q7SzseC_geS5NFtRGhYrSCT8HgxUzlF0zCfjxT4OOihjroUBjYbEnBa3nyS11jnwM6B-RS4nALTxRglIPOuG4iBmSOF1gczHegkIJDehQwFqd-I7UKjlrJrbUSYvHBDi8CPMQLT1y8K16kMQlgSl3joWQFrURsrKv5pizirviizbMzhBDwi-rbIkx3V5XEccxq5OCoqVFIXkCdShvW4bMmwLf8">Attempt This Online!</a>): ```python from time import time from timeit import repeat setup = ''' n = 10000000 r = tuple(range(n)) ''' exec(setup) for code in [ 'for i in r: i * 10', 'for i in r: (i << 3) + (i << 1)', 'for i in r: i // 10', '''for i in r: q = (n >> 1) + (n >> 2) q = q + (q >> 4) q = q + (q >> 8) q = q + (q >> 16) q = q >> 3 r = n - (q << 3) - (q << 1) q + ((r + 6) >> 4)''', ]: t = min(repeat(code, setup, number=1)) rc = repr(code) print(f'{t:.3f} seconds ', rc[:40] + '...' * (len(rc) > 40)) ``` Benchmark 2 (<a href="https://ato.pxeger.com/run?1=bVFBTsMwEBRXv2JuttOUNg1UVdX2IwghoLZqCTuJ6yAhxEu49AIv4DW8hnVsoh66B2t3dndmvfv53b6FQ-NOp68-6Onq9-pH-8YiGKtMgLFt4wO8atVjYOyoQt9iC8452yuNvXl9qObCyTUDWUcp4bDboZKYZHchx1wXwS6CN5fA1SWwWp6jBNRD6Cl0mMaizQa1HN0qlXua1LvEIzy9S5l1h8Ft_3I-eK6mgRPZJLtExhwp1SgKVPPBWPw8043Hc7NXMA533GE2ozwvwceVxMChyPAoyO-TZCBaa5xIqxWRq8Sw3xKut0_Kb0lQyoFh6Gi9cUFo_h7Wt9cL_QF7BFHHTpmOl2_4f8s_">Attempt This Online!</a>): ```python from timeit import repeat setup = ''' def div_10(n): q = (n >> 1) + (n >> 2) q = q + (q >> 4) q = q + (q >> 8) q = q + (q >> 16) q = q >> 3 r = n - (q << 3) - (q << 1) return q + ((r + 6) >> 4) def mul_10(n): return (n << 3) + (n << 1) n = 3 ** 1000000 ''' for code in ['n // 10', 'div10(n)', 'n * 10', 'mul10(n)']: t = min(repeat(code, setup, number=100)) * 10 print(f'{t:5.2f} ms ', code) ```

StefanPochmann on March 27, 2024, 2:37 p.m.
Oh, actually my benchmark for large numbers is somewhat meaningless, since `div10` doesn't work for large numbers. Or even for relatively small numbers. For example it says that 40000000000 divided by 10 is 3999999_999. Which is of course particularly bad in this mission about the last digit(s).

przemyslaw.daniel on March 27, 2024, 6:41 p.m.
if I good remember it works up to 4 bytes

StefanPochmann on March 27, 2024, 10:19 p.m.
Yes, seems to be designed for that (judging by the article you linked to).

Strings and Integers

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!