# Best way to divide by 2^n?

What would be the best way to divide an integer by 2^n in SAGE, where n is unknown? Specifically, I want to determine the value of x in integers of the following form (2^n)*x, where x is odd and I don't know n. ATM, I'm dividing by 2, then test whether result is 1 (mod2) and repeat if necessary. Is there a better way?

edit: I prefer not to use factor() as x may be large (which would make factor() slow). I just want to identify x, not its factors.

Thanks CL

edit retag close merge delete

Sort by » oldest newest most voted

In general, the largest k such that p^k divides n is named the p-adic valuation if n (when p is prime), which you can use as follows:

sage: a = 1260789648629655684939243820863888673792
sage: a.valuation(2)
10


You can see that it is much faster than factor:

sage: %timeit a.valuation(2)
The slowest run took 19.54 times longer than the fastest. This could mean that an intermediate result is being cached
1000000 loops, best of 3: 1.17 µs per loop

sage: %timeit a.factor()
10 loops, best of 3: 90.6 ms per loop


In your specific case where p=2, since numbers are represented in binary in the computer, there is an even faster method that just has to remove trailing zeros:

sage: a.odd_part()
1231239891239898129823480293812391283
sage: a/2^10
1231239891239898129823480293812391283
sage: a >> a.valuation(2)                                   # shift
1231239891239898129823480293812391283


Which looks slightly faster that shifting the binary internal representation of a:

sage: %timeit a >> a.valuation(2)
The slowest run took 23.46 times longer than the fastest. This could mean that an intermediate result is being cached
1000000 loops, best of 3: 1.45 µs per loop

sage: %timeit a.odd_part()
The slowest run took 70.98 times longer than the fastest. This could mean that an intermediate result is being cached
1000000 loops, best of 3: 282 ns per loop

more

That was very informative. Thanks for the answer.

( 2015-04-02 16:15:22 +0200 )edit

## Stats

Seen: 330 times

Last updated: Apr 02 '15