Geek Answers Handbook

Understanding the Wikipedia entry about Dragon Curves

I play with Project Euler Problem 220 , and I got a little confused in the Wikipedia article on Dragon Curve . On the issue of calculating the direction of the nth turn without having to draw the entire curve, he says:

First, express n as k * 2 ^ m, where k is an odd number. The direction of the nth turn is determined by k mod 4, that is, the remainder remains on the left when k is divided by 4. If k mod 4 is 1, then the nth turn is R; if k mod 4 is 3, then the nth revolution is L.

For example, to determine the direction of rotation of 76376:

76376 = 9547 x 8.
9547 = 2386x4 + 3
so 9547 mod 4 = 3
so turn 76376 is L
  • Is there any reasonable way to find out if n can be expressed as k2 ^ m, besides checking divisibility by successive powers of 2?
  • What does it mean if n cannot be expressed this way?

(The problem is calculating the position of the point on the Dragon curve with a length of 2 ^ 50, so actually drawing a curve is out of the question.)

+3
source share
2 answers

m is the number of zero bits at the least significant end of the number. The simplest algorithm is to divide by 2 until the number is even, but you can also use binary search to speed it up.

All integers can be expressed in this way.

+3
source

k * 2 ^ m, k . , , . ( ), . . m. k. k ( , , ), k .

k m, , , ( Python):

def k_and_m(n):
    k, m = n, 0
    while (k % 2) == 0:
        k >>= 1
        m += 1
    return k, m
+1

More articles:


All Articles