Category Archives: Math

Prefix Notation (Lisp Style)

By Zevan | February 4, 2010

Today's quiz is not multiple choice. Instead, your task is to write a lisp style math parser. This may sound tricky, but it's surprisingly simple. (well... not simple exactly, it's just simple compared to what one might assume).

Lisp uses prefix notation... where the operator is placed before the operands:

10 * 10

becomes:

* 10 10

You could think of this as a function "*" with two arguments (10, 10). In Lisp this is enclosed with parens:

(* 10 10)

Let's see a few more examples:

100 / 2 + 10

becomes:

(+ (/ 100 2) 10)

...
2 * 4 * 6 * 7

becomes:

(* 2 4 6 7)

...

(2 + 2) * (10 - 2) * 2

becomes

(* (+ 2 2) (- 10 2) 2)

Remember, thinking "functions" really helps. The above can be though of as:

multiply( add(2, 2), subtract(10 , 2), 2)

You should create a function called parsePrefix() that takes a string and returns a number:

Here is some code to test if your parser works properly:

CLICK HERE TO COPY
Actionscript:
  1. trace(parsePrefix("(* 10 10)"));
  2.  
  3. trace(parsePrefix("(* 1 (+ 20 2 (* 2 7) 1) 2)"));
  4.  
  5. trace(parsePrefix("(/ 22 7)"));
  6.  
  7. trace(parsePrefix("(+ (/ 1 1) (/ 1 2) (/ 1 3) (/ 1 4))"));
  8.  
  9. /* Should trace out:
  10. 100
  11. 74
  12. 3.142857142857143
  13. 2.083333333333333
  14. */

I highly recommend giving this a try, it was one of those cases where I assumed it would be much trickier than it was.

I've posted my solution here.

Also posted in Quiz | Tagged , , , , | 4 Comments

Float as a Fraction

By Zevan | November 29, 2009
CLICK HERE TO COPY
Actionscript:
  1. // print some floats as fractions
  2. printFraction(0.5);
  3. printFraction(0.75);
  4. printFraction(0.48);
  5.  
  6. // try something a little more complex
  7. var float:Number = 0.98765432;
  8. trace("\na more complex example:");
  9. printFraction(float);
  10. var frac:Array = asFraction(float);
  11. trace("double check it:");
  12. trace(frac[0] + "/" + frac[1] +" = " + frac[0] / frac[1]);
  13.  
  14. /* outputs:
  15. 0.5 = 1/2
  16. 0.75 = 3/4
  17. 0.48 = 12/25
  18.  
  19. a more complex example:
  20. 0.98765432 = 12345679/12500000
  21. double check it:
  22. 12345679/12500000 = 0.98765432
  23. */
  24.  
  25.  
  26. function printFraction(n:Number):void{
  27.     var frac:Array = asFraction(n);
  28.     trace(n + " = " + frac[0] + "/" + frac[1]);
  29. }
  30.  
  31. // takes any value less than one and returns an array
  32. // with the numerator at index 0 and the denominator at index 1
  33. function asFraction(num:Number):Array{
  34.     var decimalPlaces:int = num.toString().split(".")[1].length;
  35.     var denom:Number = Math.pow(10, decimalPlaces);
  36.     return reduceFraction(num * denom, denom);
  37. }
  38.  
  39. // divide the numerator and denominator by the GCF
  40. function reduceFraction(numerator:int, denominator:Number):Array{
  41.     // divide by the greatest common factor
  42.     var divisor:int = gcf(numerator, denominator);
  43.     if (divisor){
  44.         numerator /= divisor;
  45.         denominator /= divisor;
  46.     }
  47.     return [numerator, denominator];
  48. }
  49.                    
  50. // get the greatest common factor of two integers
  51. function gcf(a:int, b:int):int{
  52.     var remainder:int;
  53.     var factor:Number = 0;
  54.     var maxIter:int = 100;
  55.     var i:int = 0;
  56.     while (1){
  57.         if (b> a){
  58.            var swap:int = a;
  59.            a = b;
  60.            b = swap;
  61.         }
  62.         remainder = a % b;
  63.         a = b;
  64.         b = remainder
  65.         if (remainder == 0){
  66.             factor = a;
  67.             break;
  68.         }else if (remainder==1){
  69.             break;
  70.         }else if (i> maxIter){
  71.             trace("failed to calculate gcf");
  72.             break;
  73.         }
  74.         i++;
  75.     }
  76.     return factor;
  77. }

This snippet contains a few functions for calculating fractions based on float values. Writing this brought back some memories from grade school math.

Also posted in misc | Tagged , , | 4 Comments

Greatest Common Factor (divisor)

By Zevan | November 28, 2009
CLICK HERE TO COPY
Actionscript:
  1. trace(gcf(75,145));
  2.  
  3. // outputs 5
  4.  
  5. function gcf(a:int, b:int):int{
  6.     var remainder:int;
  7.     var factor:Number = 0;
  8.     while (1){
  9.         if (b> a){
  10.            var swap:int = a;
  11.            a = b;
  12.            b = swap;
  13.         }
  14.         remainder = a % b;
  15.         a = b;
  16.         b = remainder
  17.         if (remainder == 0){
  18.             factor = a;
  19.             break;
  20.         }else if (remainder==1){
  21.          
  22.             break;
  23.         }
  24.     }
  25.     return factor;
  26. }

I was messing around with Egyptian Fractions and found myself in need of some interesting functions. The first function I realized I would be needing was for a greatest common factor (GCF or GCD).

The above snippet is a quick implementation of Euclid's algorithm. It will return 0 if no GCF is found...

I wrote a few helper functions while working with Egyptian fractions... will post them over the next few days.

Posted in Math | Tagged , , | 4 Comments

Ancient Egyptian Multiplication

By Zevan | November 27, 2009
CLICK HERE TO COPY
Actionscript:
  1. egyptianMultiply(12, 99);
  2.  
  3. // trace(12 * 99) // test to make sure it works
  4.  
  5. /* outputs:
  6. /64 768
  7. /32 384
  8.  16 192
  9.  8 96
  10.  4 48
  11. /2 24
  12. /1 12
  13. ---
  14. 1188
  15. */
  16.  
  17.  
  18. function egyptianMultiply(valueA:Number, valueB:Number):void {
  19.    
  20.     var left:Array = [];
  21.     var right:Array = []
  22.    
  23.     // swap if valueB is smaller than value A
  24.     if (valueB <valueA){
  25.         var swap:int = valueB;
  26.         valueB = valueA;
  27.         valueA = swap;
  28.     }
  29.    
  30.     // create left and right columns
  31.     var currentLeft:int = 1;
  32.     var currentRight:int = valueA;
  33.    
  34.     while (currentLeft <valueB){
  35.         left.push(currentLeft);
  36.         right.push(currentRight);
  37.         currentRight += currentRight;
  38.         currentLeft += currentLeft;
  39.     }
  40.    
  41.    
  42.     // add up the right column based on the left
  43.     currentLeft = 0;
  44.     var rightSum:int;
  45.     var leftSum:int;
  46.     var i:int = left.length - 1;
  47.    
  48.     while (currentLeft != valueB){
  49.      
  50.       leftSum = currentLeft + left[i];
  51.       // if the next number causes the sum
  52.       // to go above valueB, skip it
  53.       if (leftSum <= valueB){
  54.         currentLeft = leftSum;
  55.         rightSum += right[i];
  56.         trace("/" + left[i]  + " " + right[i]);
  57.       } else {
  58.         trace(" " + left[i]  + " " + right[i]);
  59.       }
  60.       i--;
  61.     }
  62.     trace("---");
  63.     trace(rightSum);
  64. }

Someone mentioned egyptian multiplication to me yesterday... So read a little about it here and whipped up this example. For some reason I decided to do it in processing ... once it worked I ported it to ActionScript.

The above link describing the technique I used is from http://www.jimloy.com/... I haven't spent much time digging around the site, but it appears to have some pretty nice stuff on it...

If you're curious, here is the original processing version:

CLICK HERE TO COPY
JAVA:
  1. Vector left = new Vector();
  2. Vector right = new Vector();
  3.  
  4. int valueA = 10;
  5. int valueB = 8;
  6.  
  7. if (valueB <valueA){
  8.     int swap = valueB;
  9.     valueB = valueA;
  10.     valueA = swap;
  11. }
  12.  
  13. int currentLeft = 1;
  14. int currentRight = valueA;
  15. while (currentLeft <valueB){
  16.     left.add(currentLeft);
  17.     right.add(currentRight);
  18.     currentRight += currentRight;
  19.     currentLeft += currentLeft;
  20. }
  21.  
  22. currentLeft = 0;
  23.  
  24. int result = 0;
  25. int i = left.size() - 1;
  26. while (currentLeft != valueB){
  27.  
  28.   int temp = currentLeft + (Integer) left.get(i);
  29.   if (temp <= valueB){
  30.    
  31.     currentLeft = temp;
  32.     result += (Integer) right.get(i);
  33.     println("/" + left.get(i) + " " + right.get(i));
  34.   } else {
  35.     println(" " + left.get(i)  + " " + right.get(i));
  36.   }
  37.    
  38.   i--;
  39. }
  40. println("---");
  41. println(result);

After writing, this I took a look at the wikipedia entry... I also found myself on this short page about a scribe called Ahmes. (I recommend reading this if you are interested in PI)

Also posted in misc | Tagged , , , | 1 Comment