Re: Re: simplifying ulam spiral code
- To: mathgroup at smc.vnet.net
- Subject: [mg56494] Re: [mg56456] Re: simplifying ulam spiral code
- From: DrBob <drbob at bigfoot.com>
- Date: Tue, 26 Apr 2005 21:53:05 -0400 (EDT)
- References: <d4cmlr$39e$1@smc.vnet.net> <d4hvsv$1jp$1@smc.vnet.net> <200504260533.BAA14380@smc.vnet.net>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
Here's an admittedly trivial simplification:
coords[k_List] := Module[{n, a, b, c}, n = Floor[Sqrt[k + .1]];
a = k - n(n + 1);
c = 1 - 2Mod[n, 2];
b = Quotient[2n + 1 - c, 4];
c Transpose[{Quotient[Abs[a] + a, 2] - b, Quotient[Abs[a] - a, 2] - b}]]
"c = 2Mod[n, 2, -1] + 1" seemed a bit tortured, to me.
Bobby
On Tue, 26 Apr 2005 01:33:03 -0400 (EDT), Carl K. Woll <carlw at u.washington.edu> wrote:
> "Carl K. Woll" <carlw at u.washington.edu> wrote in message
> news:d4hvsv$1jp$1 at smc.vnet.net...
>> "zak" <chocolatez at gmail.com> wrote in message
>> news:d4cmlr$39e$1 at smc.vnet.net...
>>> hi
>>> in the site:
>>> http://teachers.crescentschool.org/weissworld/m3/spiral/spiral.html
>>> there is a mathematica code for drawing ULAM'S SPIRAL
>>> the code is:
>>>
>> [snip]
>>
>> I have to confess that I don't understand how zak's code relates to the
>> above link. The text at the link says that 1 is placed at the origin, 2 is
>> placed to the right of 1, and succeeding integers are placed in a
>> counterclockwise spiral. Hence, 3 ought to have the coordinates {1,1}, 4
>> ought to have the coordinates {0,1}, etc.
>>
>> At any rate, it is not too difficult to program a function to determine
>> the
>> coordinates of an integer in the above spiral. If one notices that the
>> bottom right and top left corners have the integer values n^2+1, then one
>> eventually gets
>>
>> coords[k_Integer] := Module[{n, a, b},
>> n = Floor[Sqrt[k - .9]];
>> a = k - n^2 - n - 1;
>> b = Quotient[2n + 1 - (-1)^n, 4];
>> (-1)^n {Quotient[Abs[a] + a, 2] - b, Quotient[Abs[a] - a, 2] - b}]
>>
>> coords[k_List] := Module[{n, a, b, c},
>> n = Floor[Sqrt[k - .9]];
>> a = k - n^2 - n - 1;
>> c = (-1)^n;
>> b = Quotient[2n + 1 - c, 4];
>> c Transpose[{Quotient[Abs[a] + a, 2] - b, Quotient[Abs[a] - a, 2] -
>> b}]]
>>
>> A few comments may be in order. Concentrating on the second function
>> definition, I used a number of ideas to speed up it's execution. I used
>> Sqrt[k-.9] so that Mathematica is taking square roots of real numbers
>> instead of integers, which perhaps surprisingly is much faster. I used
>> Sqrt[k-.9] instead of Sqrt[k-1.] to avoid spurious cancellation errors
>> when
>> the Floor of the result is evaluated. I wanted to make sure that all my
>> arrays were packed, so I used Quotient instead of dividing two integers.
>> Even though 2n+1-(-1)^n is always divisible by 4, (2n+1-(-1)^n)/4 is not
>> packed even when 2n+1-(-1)^n is packed. Finally, I used (Abs[a]+a)/2 (with
>> Quotient instead of using division) to change all negative values in the
>> list a to 0 and (Abs[a]-a)/2 to change all positive values in the list a
>> to
>> 0.
>>
>> At any rate, using coords on a list of the first million integers takes a
>> bit less than 2 seconds on my machine.
>>
>> Now, we are ready to used coords to find the coordinates of the primes.
>> For
>> example, if we are interested in the first million primes:
>>
>> data = Prime[Range[10^6]]; // Timing
>> {9.547 Second, Null}
>>
>> Now, we use coords to get the coordinates of the primes.
>>
>> pts = coords[data]; // Timing
>> {2.375 Second, Null}
>>
>> Applying Developer`ToPackedArray to the data would speed up the pts
>> computation by a bit. Looking at the first few points of pts reveals
>>
>> Take[pts, 10]
>> {{1, 0}, {1, 1}, {-1, 1}, {-1, -1}, {2, 0}, {2, 2}, {-2, 2}, {-2, 0},
>> {0, -2}, {3, 1}}
>>
>> which looks correct to me.
>>
>> Carl Woll
>>
>>
>
> I see now that I started with 1 at the origin, and others started with 0 at
> the origin. Hence, a small modification of my code will return results that
> agree with e.g., Daniel Lichtblau.
>
> coords[k_List] := Module[{n, a, b, c},
> n = Floor[Sqrt[k + .1]];
> a = k - n(n + 1) ;
> c = 2Mod[n, 2, -1] + 1;
> b = Quotient[2n + 1 - c, 4];
> c Transpose[{Quotient[Abs[a] + a, 2] - b, Quotient[Abs[a] - a, 2] - b}]]
>
> Basically, I substituted k+1 for k. I also got rid of Power by using n(n+1)
> to evaluate n^2+n and I by using Mod to find (-1)^n. These latter changes
> increased the speed of coords by about 33%.
>
> Carl Woll
>
>
>
>
>
--
DrBob at bigfoot.com
- References:
- Re: simplifying ulam spiral code
- From: "Carl K. Woll" <carlw@u.washington.edu>
- Re: simplifying ulam spiral code