Ask Your Question
1

Best way to divide by 2^n?

asked 2015-04-02 05:23:37 +0200

updated 2015-04-02 07:12:21 +0200

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 flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2015-04-02 09:58:40 +0200

tmonteil gravatar image

updated 2015-04-02 10:23:03 +0200

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
edit flag offensive delete link more

Comments

That was very informative. Thanks for the answer.

Choose a screen name gravatar imageChoose a screen name ( 2015-04-02 16:15:22 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-04-02 05:23:37 +0200

Seen: 304 times

Last updated: Apr 02 '15