Understanding the wikipedia entry on Dragon Curves

I'm playing around with Project Euler's Problem 220, and I'm a little confused about the Wikipedia article on the topic, Dragon Curve. On the topic of calculating the direction of the nth turn without having to draw the entire curve, it says:

First, express n in the form k * 2^m where k is an odd number. The direction of the nth turn is determined by k mod 4 i.e. the remainder 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 turn is L.

For example, to determine the direction of turn 76376:

76376 = 9547 x 8. 9547 = 2386x4 + 3 so 9547 mod 4 = 3 so turn 76376 is L

  • Is there a clever way to figure out if n can be expressed as k2^m, apart from checking divisibility by successive powers of 2?
  • What does it mean if n cannot be expressed in such a way?

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

-------------Problems Reply------------

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

All integers can be expressed in this way.

Any integer can be expressed as k * 2^m where k is odd. To see why, write any number in binary. Starting from the right (least significant bit), there will be a string of all zeros. It might be an empty string. The number of zeros is m. The rest of the bits make up k. k's least significant bit is a one (because if it were a zero, you'd simply extend your string of zeros), so k is odd.

To find k and m, you'll probably write a simple loop (Python in this case):

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

Category:fractals Views:0 Time:2008-12-29
Tags: fractals

Related post

  • Drawing a Dragons curve in Python 2009-04-19

    I am trying to work out how to draw the dragons curve, with pythons turtle using the An L-System or Lindenmayer system. I no the code is something like the Dragon curve; initial state = ‘F’, replacement rule – replace ‘F’ with ‘F+F-F’, number of repl

  • Trying to understand the wikipedia strategy pattern example using new Func 2010-01-12

    I was looking at this, http://en.wikipedia.org/wiki/Strategy_pattern and I understand the concept of the strategy pattern, but could someone explain the C# example a bit. I dont really get the how and why of the definition of 'Strategy' in the Contex

  • How to get a Wikipedia entry's template type 2011-02-06

    I need to find out the template type of a Wikipedia page entry. Up to this point, I've relied on parsing the results from a query to Wikipedia, which works to a point. For instance, if I search for Joel Spolsky, I can regex match 'infobox' and find o

  • Understanding the vtable entries 2011-04-19

    For this code: class B1 { public: virtual void f1() {} }; class D : public B1 { public: void f1() {} }; int main () { B1 *b1 = new B1(); D *d = new D(); return 0; } After compilation, the vtable I get is this: Vtable for B1 B1::_ZTV2B1: 3u entries 0

  • Understanding Routing table entry 2011-12-22

    Hello every one I want to ask a question about route command in linux.I have enter following command in linux terminal >route and got the output Destination Gateway Genmask Flags Metric Ref Use Iface 192.168.1.0 * 255.255.255.0 U 1 0 0 eth0 192.16

  • datastructure or implementation of buddy heap algo 2009-05-21

    i want to know how buddy heap algo works or what datastructure is being used in it . --------------Solutions------------- I'm guessing you're thinking of buddy memory allocation? There's the link to the Wikipedia page. It does mention: Typically the

  • how understand that a cal entry in outlook is expandable or not 2013-12-09

    how understand that a cal entry in outlook is expandable or not? --------------Solutions------------- How see that text here really exist, how understand without open all notes that a cal note have this textarea... screenshot>>> http://www.l

  • Understanding code metrics 2008-09-30

    I recently installed the Eclipse Metrics Plugin and have exported the data for one of our projects. It's all very good having these nice graphs but I'd really like to understand more in depth what they all mean. The definitions of the metrics only go

  • Help understanding this stack trace 2010-01-21

    I have health monitoring turned on, and i have the following error i'm trying to understand: Exception: Exception information: Exception type: System.InvalidCastException Exception message: Specified cast is not valid. Thread information: Thread ID:

  • truly understanding the difference between procedural and functional 2011-03-07

    So I'm really having a hard time understanding the difference between procedural and functional programming paradigms. Here are the first two paragraphs from the Wikipedia entry on functional programming: In computer science, functional programming i

  • Problem to achieve curved animation 2011-07-27

    Possible Duplicate: Android, move bitmap along a path? I want to move an image through a curved path.Is it possible in android ? I searched a lot but i can only find about scale,rotate and translate animation.So anyone have any idea please help.Is it

  • Why is my dragon fractal incomplete 2011-10-09

    I have translated the code from javascript to c# which can be found by going to this excellent demo at http://fractal.qfox.nl/dragon.js My translation is intended to produce just a single dragon upon clicking the button but I think I have missed some

  • How do I limit the number of entries in a java hashtable? 2009-01-07

    Is there a technique such that I can specify a number n such that when the (n + 1)th entry is inserted, the oldest entry is removed first ensuring that the size of the hashtable is always limited to n? --------------Solutions------------- LinkedHashM

  • Tool to parse text for possible Wikipedia links 2009-03-11

    Does a tool exist that can parse text and output that text, hyper-linked to Wikipedia entries for words of interest? For example, I'd like a tool that could turn something like: The most popular search algorithm on a sorted list is the binary search.

  • Approximating Bezier Curves of Degree N 2009-04-18

    I know there are methods to approximate cubic Bezier curves (this page was also a good reference), but is there a quicker method to approximate a bezier curve of degree N? Or can you only use the generalization below? From wikipedia: The Bézier curve

  • how is this Strategy Pattern written in Python? (the sample in Wikipedia) 2009-06-08

    In the Wikipedia entry for the Strategy Pattern: http://en.wikipedia.org/wiki/Strategy_pattern Most other code sample is doing something like: a = Context.new(StrategyA.new) a.execute #=> Doing the task the normal way b = Context.new(StrategyB.new

  • what is the best resource for understanding why GPU is more powerful than CPU 2009-10-27

    I was reading this site: http://www.nvidia.com/object/cuda_what_is.html and I wanted to find out some more generic information on the ideas behind GPU computing (including the history on using this for computation and benefits over using CPUs) Does a

  • Understanding and modifying large projects 2010-09-03

    I am a novice programmer and as a part of my project I have to modify a open source tool (written in java) which has hundreds of classes. I have to modify a significant part of it to suit the needs of the project. I have been struggling with it for t

  • Understanding C++ struct size 2011-01-09

    Consider the following code: struct CExample { int a; } int main(int argc, char* argv[]) { CExample ce1; CExample ce2; cout << "Size:" << sizeof(ce1) << " Address: " << &ce1 << endl; cout << "Size:" << si

Copyright (C) dskims.com, All Rights Reserved.

processed in 0.195 (s). 11 q(s)