Computational Algorithm

Skip to end of metadata
Go to start of metadata

Computational Algorithm #001

Factor 136059 and graphically represent every step
of your factoring algorithm using geometric objects.

Implementations

MATLAB / Brett Cropp, Brown '08.5

This approach uses the remainders of every number up to the number being factored as 'multipliers' for pixel data in a referenced image.
Image generated by MATLAB Implementation by Brett Cropp, Brown '08.5

Java, Processing / Matthew Jacobs, Brown '09

Image Generated by Java Implementation by Matthew Jacobs, Brown '09

This program implements [http://en.wikipedia.org/wiki/Pollard's_rho_algorithm|Pollard's Rho Algorithm\ for factoring large numbers. It is more efficient than the [http://en.wikipedia.org/wiki/Trial_division] approach. There is a large amount of randomness in this algorithm which is displayed in the generated image, though the image always converges to the same pattern – representative of the number being factored. Red dots indicate factors, gray dots indicate intermediate results of the 'pseudo-random walk' being computed by the algorithm.


Online Java Applet
 

 Background and Concept

Sol LeWitt reduced art to a few of the most basic shapes
(quadrilaterals, spheres, triangles), colors (red, yellow, blue,
black) and types of lines, and organized them by guidelines he felt in
the end free to bend. Much of what he devised came down to specific
ideas or instructions: a thought you were meant to contemplate, or
plans for drawings or actions that could be carried out by you, or
not. Sometimes these plans derived from a logical system, like a game;
sometimes they defied logic so that the results could not be foreseen,
with instructions intentionally vague to allow for interpretation.
(NYTimes -- read more)

I'm interested in taking a relatively simple problem: factoring large
numbers. This is a very well studied problem in mathematics and
computer science, and many algorithms exist to do this. I want to
represent an algorithm for factoring large numbers with graphical,
geometric representations for every step. The art is in the beauty of
the elegance of the algorithm which can will become visual through
geometric primitives. I like this idea because it is a relatively
simple concept which is difficult to implement, but if done correctly,
will produce beautiful results. This is similar to LeWitt's simple
concepts for line drawings which were often incredibly difficult to
implement. Just as LeWitt offered ample 'wiggle room' for his
assistants to interpret his ideas, this concept also allows the
implementor(s) to choose (a) what algorithm they will use to factor, (b)
how they will implement it (MATLAB, Processing, Java, C++, Flash, etc),
(c) which geometric primitives they will use to graphically display the steps.

Source Code

code: Invalid value specified for parameter lang

x = 136059
for(i = 1:ceil(sqrt))
a = rem(x,i);
end
[x,y] = find(a == 0);
b = (length:-1:1);
y(1,[\(length\(y\)\+1\):\(length\(y\)\*2\)]) = 136059./y(1,[b]);
y = sqrt;
bee = imread('web-link');
bee = double(bee);
bee = bee./(max(max(max(bee))));
bee(:,:,1) = bee(:,:,1).*rand(size(bee(:,:,1)));
bee(:,:,2) = bee(:,:,2).*rand(size(bee(:,:,2)));
dimrow = floor(size(bee,1)/size(y,1));
dimcol = floor(size(bee,2)/size(y,2));
factors1 = [];
for(j = 1:dimcol)
factors1 = [factors1 y];
end
factors2 = [factors1];
for(i = 2:dimrow)
factors2 = [factors2; factors1];
end
bee = bee(1:(size(factors2,1)),1:(size(factors2,2)),;
bee = bee(:,:,3).*factors2;
image(bee);

Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.