RSS
 

Cogwheels with Raphaël – part 2

05 Jun

Teething In this article we will grow teeth on our cogwheel. We start with a wheel having 12 teeth and we double that number. As explained in the last article, we have function getPath() dedicated to generating the path in string format. To animate teething we generate the new path and then morph:

teeth = 12;
paths = new Array();
paths[1] = getPath(180, 180, 120, 12, 0);
paths[2] = getPath(180, 180, 120, 24, 0);

180, 180 is the centre point, 120 is the radius, and 12 & 24 are number of teeth. The function to morph is:

function morph()
{
	teeth = 36 - teeth;
	big.animate({path:paths[teeth/12]},5000);
}

As teeth oscillates between 12 and 24, the path is set to either paths[1] or paths[2]. 5000 is the duration of the animation in milliseconds. We are ready to go. Press Morph!


Oops, something went wrong. Looks like when we double or halve the number of teeth, Raphaël is messing up the points on the path that are for teeth and the points for the holes. Read the rest of this entry »

 
1 Comment

Posted in Raphaël

 

Thoughts on Fibonacci Numbers

30 May

In 1988, round about the time I first learned of Binet’s formula

F_n = \frac{\left (1 + \sqrt{5} \right )^n - \left (1 - \sqrt{5} \right )^n}{2^n \sqrt{5}} \qquad \qquad \forall n \geq 0

which appears to have been described by de Moivre some 50 years before Binet was born, I was calculating

F_n \bmod{n}

for no good reason on my very own Casio FX730P

when a friend looked over my shoulder and made a discovery. She had noticed that

F_p \equiv \pm1 \pmod{p} \qquad \qquad \text{if }p \text{ is prime}, p \neq 5

(The prime 5 had soon to be excluded, since F5 = 5 ≡ 0 (mod 5).)

The program was modified to confirm this conjecture, at least in the Casio’s integer range. It became clear that a prime p was sufficient but not necessary, because early on we found

F_{4} \equiv -1 \pmod{4}\\F_{14} \equiv -1 \pmod{14}\\F_{22} \equiv +1 \pmod{22}\\F_{26} \equiv -1 \pmod{26}\\F_{34} \equiv -1 \pmod{34}\\F_{38} \equiv +1 \pmod{38}\\F_{46} \equiv -1 \pmod{46}\\F_{58} \equiv +1 \pmod{58}\\F_{62} \equiv +1 \pmod{62}\\F_{74} \equiv -1 \pmod{74}\\F_{82} \equiv +1 \pmod{82}\\F_{86} \equiv -1 \pmod{86}\\F_{94} \equiv -1 \pmod{94}\\

Those were all even numbers, they couldn’t be prime anyway. We were now looking for

F_n \equiv \pm1 \pmod{n} \qquad \qquad \text{where }n \text{ is odd and not prime}

Those were the first we found

F_{323} = 17 \cdot 19 \equiv +1 \pmod{323}\\F_{2737} = 7 \cdot 17 \cdot 23 \equiv +1 \pmod{2737}\\F_{4181} = 37 \cdot 113 \equiv +1 \pmod{4181}\\F_{5777} = 53 \cdot 109 \equiv -1 \pmod{5777}\\F_{6479} = 11 \cdot 19 \cdot 31 \equiv +1 \pmod{6479}\\F_{6721} = 11 \cdot 13 \cdot 47 \equiv +1 \pmod{6721}\\F_{7743} = 3 \cdot 29 \cdot 89 \equiv +1 \pmod{7743}\\

I could not find how these numbers were connected. Still, our initial conjecture was pretty cool. I showed it to a few mathematicians who assured me we were on to something. I never managed to prove it and eventually forgot about it. Then in May 2008 a paper captured my attention[1]. It includes reference to a proof in [2]. It turns out that the conjecture can be made more precise:

\text{For }p\text{ a prime, }k > 0\\F_p \equiv\begin{cases} +1 \pmod{p}, & p = 5k\pm1\\ -1 \pmod{p}, & p = 5k\pm2\end{cases}

[1] V. E. Hoggatt, Jr. and Marjorie Bicknell: Some Congruences of the Fibonacci Numbers Modulo a Prime P; Mathematics Magazine, Vol. 47, No. 4, (Sep., 1974), pp. 210-214

[2] G. H. Hardy, and E. M. Wright: An Introduction to the Theory of Numbers; 4th ed., Oxford University Press, 1960

 
No Comments

Posted in Legacy

 

Cogwheels with Raphaël – part 1

28 May

As a way to learn Raphaël I want play with cogwheels. I will build this up gradually. This is the first installment. Let’s begin with two cogs. Below is a working example of them, press the buttons to try the different easings that are supported by the Raphaël animate method.


First create canvas.

var r = Raphael("canvas", 600, 450);

Next define a cogwheel() function, that takes radius and number of teeth as arguments.
Read the rest of this entry »

 
No Comments

Posted in Raphaël

 

Pocket calculator with Raphaël – part 2: The LED display

22 May

Let’s have a look at some implementation details of the upside-down calculator mentioned in this post. What we are interested in is the LED display. Remember we are using Raphaël.

Below is one digit of the 7 segment LED. Click the buttons to control the segments and the decimal point.


Because the digit is slanted, it can easily be put into a row to form a calculator display. There is space for the decimal point. How convinient.

Now let’s look at the simplified code for this LED digit. After creating the Raphaël canvas we set a black background for the LED digit.

window.onload = function ()
{
  var r = Raphael("canvas", 240, 250);
  var display = r.rect(0,0,185,244,0).animate({fill: "#000"},0);

The digit is stored in a set. We push on the paths for the segments and a circle for the decimal point.

  led = r.set();
  led.push(
    r.path("M 11,0 L 35,0 35,1 32,4 12,4 8,1 z"),
    r.path("M 32,4 L 36,1 37,3 33,22 31,24 29,22 z"),
    r.path("M 28,27 L 30,25 31,25 32,27 29,45 28,48 25,45 z"),
    r.path("M 4,45 L 24,45 27,48 25,49 2,49 1,48 z"),
    r.path("M 6,25 L 7,27 4,44 0,48 0,47 3,27 z"),
    r.path("M 8,1 L 11,4 8,21 6,24 4,22 7,3 z"),
    r.path("M 9,22 L 28,22 30,24 28,26 8,26 6,25 6,24 z"),
    r.circle(34,47,2)
  );

After that the segments are filled with a dark grey.

  for (var i = 0; i<8; i++)
  {
    led[i].animate({fill:colourledoff, "stroke-width": 0}, 1000);
  }
}

We now need a function to switch the relevant segments on or off. First we create an array of on/off flags for every segment and every symbol, i.e. ’0′..’9′, ‘-’, and ‘E’. For example, to show a ’5′ all segments are on apart from segments 2 and 5. We also define the colours to use for the segments.

var colourledon  = "#0F0";
var colourledoff = "#444";

var segments = [];
segments['0'] = new Array(1,1,1,1,1,1,0);
segments['1'] = new Array(0,1,1,0,0,0,0);
segments['2'] = new Array(1,1,0,1,1,0,1);
segments['3'] = new Array(1,1,1,1,0,0,1);
segments['4'] = new Array(0,1,1,0,0,1,1);
segments['5'] = new Array(1,0,1,1,0,1,1);
segments['6'] = new Array(1,0,1,1,1,1,1);
segments['7'] = new Array(1,1,1,0,0,0,0);
segments['8'] = new Array(1,1,1,1,1,1,1);
segments['9'] = new Array(1,1,1,1,0,1,1);
segments['-'] = new Array(0,0,0,0,0,0,1);
segments['E'] = new Array(1,0,0,1,1,1,1);

This array is used in the update() function, which takes one character as its argument:

function update(num)
{
  var x=7;
  while (x--)
  {
    if (segments[num][x])
    {
      led[x].animate({fill:colourledon}, 1000);
    }
    else
    {
      led[x].animate({fill:colourledoff}, 1000);
    }
  }
}

A similar function controls the decimal point.

function decimal(pChecked)
{
  if (pChecked)
  {
    colour=colourledon;
  }
  else
  {
    colour=colourledoff;
  }
  led[7].animate({fill:colour}, 1000);
}

This was the simplified code for one digit. In the calculator code the digit is cloned into an array of LED digits:

/* clone single LED */
var ledrow=[];
ledrow[0] = led;
var z=10;
while (z--)
{
  ledrow[10-z] = ledrow[9-z].clone();
  ledrow[10-z].translate(-41,0)
}

When you flip the display and you have a really slow computer you might see the segments being dragged behind as shown in the following screenshot:

 
No Comments

Posted in Raphaël

 

micro-PROLOG: variable names

14 May

micro-PROLOG variable names consist of a prefix character followed by an optional subscript number. Here are the details:

    prefix character : X | Y | Z | x | y | z
    subscript number : 0..127

The string of digits that form the subscript is interpreted as a number and internally stored as such against a variable prefix. This is not the prefix given by yourself. Rather, prefixes are dished out in the order

    X, Y, Z, x, y, z

Read variable names like so:

    Y3 => Y3
    x14 => x14
    z027 => z27 => z27
    X => X0 => X0
    Y312 => Y56 => Y56

Note how 027 is equivalent to 27. Further notice that a variable prefix on its own implies subscript 0. The last line illustrates another peculiarity. Subscripts are in the range 0..127. The variable name Y312 will internally be represented as Y56.

Since values are stored against a prefix and its subscript, the variable name that was used when the variable has been defined is lost and cannot be restored. Prefix and subscript depend on the position of the variable in a clause. Confused?

Let’s try this. Gives us a chance to interact with the system. First we enter a program:

&.((Reverse y26 X40)
1.   (Reverse y026 () X40))
&.(Reverse (x0|Y2) x2 z0)
1.   (Reverse Y2 (x|x2) z0))
&.(Reverse () z z)
&.

The variable names are a bit silly, but this is for demonstration purposes. Now let’s run the program.

&.?((Reverse (1 2 3 4 5 6) x8) (P x8))
(6 5 4 3 2 1)
&.

It works. Time to list the Reverse program:

&.LIST (Reverse)
&.((Reverse X Y)
1.   (Reverse X () Y))
&.(Reverse (X|Y) Z x)
1.   (Reverse Y (X|Z) x))
&.(Reverse () X X)
&.

If this is what you have expected then give yourself a pat on the shoulder.

What’s this about? The reason for this strange naming convention is simply the fact that the tokeniser has to make a distinction between variable names and constants. If it is not a variable name it is a constant.

These are not variable names:

    K023
    Name
    post_code
    $temp
    X_01

Stuck with it? No, not at all. The syntax rules were provided in an editable file and could thus be changed. For example, the prefix characters could be changed from

    X | Y | Z | x | y | z

to

    a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

making all tokens starting with a lowercase letter followed by a number a variable name, and the rest a constant.

 
1 Comment

Posted in Legacy

 

<isindex> tag

09 May

To send data to a www server the http client posts form data by either the GET or the POST method. But this was not always the case. The form tag has only been introduced in HTML 2.0 (IETF RFC 1866). The first specification, known as “Hypertext Markup Language (HTML)” Internet-Draft, does not mention forms. This specification describes another mechanism to allow clients to initiate searches on the server. Surprisingly, this method is still supported by many browsers.

<isindex> All that is needed is adding the isindex tag to the head of the html document:

<html>
<head>
<isindex>
...
</head>
<body>
...

This tag would tell the browser that this document is searchable (is an index). The browser now has to provide means for the user to enter search terms. As an example here a screenshot of how Mosaic 1.0 did this in 1993. Read the rest of this entry »

 
No Comments

Posted in Legacy

 

Animated GIFs – part 2

06 May

I saw a wooden model of such a gear in 1982, and always wanted to build one myself. Instead I’ve modelled it in AutoCAD and created this GIF (around 1998).

gear

 
No Comments

Posted in Legacy

 

micro-PROLOG: programs

05 May

In 1987 I started learning PROLOG. I had a copy of micro-PROLOG, which had been developed at the Imperial College in London. I liked the LISP-like syntax and loved learning micro-PROLOG.

Here you can see my original 8″ floppy. If only I had a drive to read it, I would be able to play with the interpreter again! For those who don’t know what 8″ are I have included a smartcard for reference. Click to enlarge.

Programs What is called a function or a routine in other systems is called a program in micro-PROLOG. Here are the famous two clauses that define the append program. The ampersand is the supervisor prompt, the dot the prompt of the read function. Note that on line three there is no supervisor prompt as the clause has not been entered completely. The read function displays the number of open parentheses and its prompt, the dot, to say it is ready for more input.

&.((Append () x x))
&.((Append (x|X) Y (x|Z))
1.     (Append X Y Z))
&.

Before we try and run a program, let’s look at the SUM program for a moment. Here are examples of how it can be used:

    (SUM 3 4 x) yields x = 7
    (SUM 1 x 9) yields x = 8
    (SUM x 5 11) yields x = 6

But there is another way to use it. Can you guess?

    (SUM 17 26 43) succeeds
    (SUM 13 42 54) fails

To execute a program, the run command “?” is used. The run command will only report if the goal succeeded or failed. If the goal succeeds, the run command finishes silently and the supervisor prompt is shown. The supervisor is ready for new input.

&.?(SUM 1 x 9)
&.

If the goal fails, run will print a “?” before handing over to the supervisor:

&.?(SUM 13 42 54)
?
&.

To see the actual result of a calulation, a print instruction needs to be included in the goal. As an example we use PROD which does multiplication:

&.?((PROD x 7 35) (PP The result is x))
The result is 5
&.

SUM and PROD are built-in programs. Needless to say, there are no programs for subtraction and division. One more interesting fact about the PROD program shall be mentioned here. It can be matched with four arguments, the last being the remainder of the division:

&.?((PROD 4 x 19 y) (PP factor x remainder y))
factor 4 remainder 3
&.

To round off this post, we finally run the append function we defined at the beginning of his post. First we append one list to another.

&.?((Append (1 2) (3 4) x) (P x))
(1 2 3 4)
&.

Next find the missing sub-list:

&.?((Append x (6 7) (3 4 5 6 7)) (P x))
(3 4 5)
&.?((Append (1 2) x (1 2 3 4 5 6 7)) (P x))
(3 4 5 6 7)
&.

Split a list:

&.?((Append x y (1 2 3 4 5)) (P x y))
() (1 2 3 4 5)
(1) (2 3 4 5)
(1 2) (3 4 5)
(1 2 3) (4 5)
(1 2 3 4) (5)
(1 2 3 4 5) ()
&.

I know what you are thinking now. Can we use PROD for factorisation?

&.?((PROD x y 60) (LESS x y) (P x y))
1 60
2 30
3 20
4 15
5 12
6 10
&.

Unfortunately, the built-in PROD program does not support this.

Features There are other topics I would like to write about. I plan to do a short post on tail recursion, optimisation, the list constructor, and even on variable names.

 
No Comments

Posted in Legacy

 

Animated GIFs – part 1

04 May

When I was a webmaster for the first time, webpages were pretty static. With my provider (demon) anyway. The only way to make anything move was an animated GIF.

This train started as a cartoon from a book. There it had a diesel engine. I have ruined the joke by replacing that with a steam engine. Then I made it go round the track (1996).

train

The animation consists of 27 images. To safe space an optimizer was run to find those areas of a frame that have changed in relation to the previous frame. Only the first image is full size, the rest merely update an area. The next image shows this in slow motion:

Note that the train is pulling a ‘tail’ of empty space. This is to get rid of the end of the last carriage.

The animation was created with Advanced GIF Animator, a Canadian software if memory serves, and the killer app of the day.

 
No Comments

Posted in Legacy

 

Prime numbers in BASIC

03 May

In the beginning were … prime numbers. For some reason I just had to write a program that printed out a long list of prime numbers. Nobody knows why. Those were the early 80s!

The resulting code was both short and fast:

A = 1 :  D = 4
A = A + D : D = 6 - D : B = 5 : C = 2 : L = INT(SQRT(A))
IF B > L THEN PRINT A : GOTO 2
IF A MOD B = 0 THEN GOTO 2
B = B + C : C = 6 - C : GOTO 3
END

So how what does the code do? Three ideas have been used:

  1. only do primality test for numbers of the form 6k±1
  2. only test factors up to the root of a candidate number
  3. only use factors of form 6k±1

Points 1 and 3 mean we are not even looking at numbers that are divisible by 2 or 3. This is easily implemented by alternately adding 2 and 4 to the current number, starting with number 5.

Variable A holds the candidate, variable D holds either 2 or 4. The new candidate is determined by incrementing A by D. This, and the alteration of D, is accomplished in line 2. B is the factor to be tested, and C alternates between 2 and 4 to determine the next factor. B and C are initialized in the same line. Here we also calculate the square root of the candidate. We store it in L for later use.

A = 1 :  D = 4
A = A + D : D = 6 - D : B = 5 : C = 2 : L = INT(SQRT(A))
IF B > L THEN PRINT A : GOTO 2
IF A MOD B = 0 THEN GOTO 2
B = B + C : C = 6 - C : GOTO 3
END

We now check if the factor is greater than the root we saved in L, and if it is, we have found a prime number, print it out and increment A.

A = 1 :  D = 4
A = A + D : D = 6 - D : B = 5 : C = 2 : L = INT(SQRT(A))
IF B > L THEN PRINT A : GOTO 2
IF A MOD B = 0 THEN GOTO 2
B = B + C : C = 6 - C : GOTO 3
END

Otherwise we want to know if A is divisible by B, and if it is we know A is not prime, and increment A by D:

A = 1 :  D = 4
A = A + D : D = 6 - D : B = 5 : C = 2 : L = INT(SQRT(A))
IF B > L THEN PRINT A : GOTO 2
IF A MOD B = 0 THEN GOTO 2
B = B + C : C = 6 - C : GOTO 3
END

But if B was no factor, we have to increment it by C, adjust C, and continue to see if B has reached the root L, etc.:

A = 1 :  D = 4
A = A + D : D = 6 - D : B = 5 : C = 2 : L = INT(SQRT(A))
IF B > L THEN PRINT A : GOTO 2
IF A MOD B = 0 THEN GOTO 2
B = B + C : C = 6 - C : GOTO 3
END

Note that line 6 is never reached. At some point there will be an integer overflow and the program execution will stop.

Javascript The best way to test the algorithm on this page is to run it in Javascript. Please generate prime numbers up to one million, then two million, then five, and finally ten million:


This is the Javascript code:

function prime(pL)
{
   var pp = 'Print all primes < '+pL+'<hr>2 3 ';

   for (var a=5,d=2;a<=pL;a+=d,d=6-d)
   {
      for (var b=5,p=true,c=2,r=parseInt(Math.sqrt(a));b<=r;b+=c,c=6-c)
         {if (a % b == 0) {p=false;break;}}
      if (p) pp+=(a+' ');
   }
   document.write(pp);
}

The timer is stopped after line 10, just before the string pp is written out.

 
No Comments

Posted in Legacy