Middle Squares and Big Nums

No screen shots tonight. But on the semi-bright side, at least this time I am posting something that has to do with TAOCP.

For my second quick experiment to play with the Flash tools, I decided to make a swf that would illustrate the "middle-square" method for pseudo-random sequences of numbers (aka a pseudo-random number generator, or PRNG).

The technique is simple, and aptly named at least if you are used to reading your function compositions as (f ○ g) rather than as the categorical style of (g ; f). Every time you want a new "random" number of let's say 10 digits, you take the previous number N (or the initial seed if you're just starting out), square it (which will yield of number of at most 20 digits, and in fact we'll pad N² out with zeroes so that it is always 20 digits), and then extract the middle 10 digits from that 20 digit N².

It shouldn't take very much code to implement something like this. Except (a ha), a lot of "modern" languages like ActionScript do not have built-in support for arbitrary precision arithmetic. In the particular case of the ECMAscript family, as soon as you get above a certain threshold (usually around 2³⁰ or so, they fall into floating-point mode. That might suffice for a lot of the scripts out there, but it falls down miserably in this case because the majority of the ten digit numbers are obviously larger than 5⋅10⁹ = 5,000,000,000 which is itself larger than 4,294,967,296 = 2³².

So as soon as you want to actually show off Knuth's first example: 5,772,156,649, you discover that you can't use the language's built-in arithmetic to do it.

(And for those of you saying "but it is safe to use floating point to store those ten digit numbers; you get 53 bits of precision in the significand in IEEE 754 floating point": I recommend you go back up and re-read the very first step (or second-word in our ○-composed name). And/or double-check what 2⁵³ is in base-10.

Anyway, that was just a long explanation for why I had to make a quick BigNum class in order to do this task. I wasn't expecting to have to get into BigNum work until I hit Chapter 4 of TAOCP, and I plan to keep the class as minimal as possible (in both performance and features) until I get there.

(I used Emacs htmlize.el to format this code. If I knew how to integrate the CSS it generates into blogspot, I'd have font colors too. But that will have to be a project for another day.)

BigNum.as code

package  {
    public class BigNum {
        internal static const bigitLen = 16;
        internal static const base = 10; // Math.pow(2, bigitLen);

        // a base of 10 is *incredibly* inefficient, but it does allow
        // for a very simple toString implementation (and parse as well
        // but lets only put that in if I need to debug)

        public function toString():String {
            // This code *definitely* only works for base == 10

            if (base == 10) {
                var i;
                var r = "";
                var maxNonZeroIdx = 0;
                for (i=0; i < bigits.length; i++) {
                    if (bigits[i] > 0) {
                        maxNonZeroIdx = i;
                    }
                }
                for (i=0; i <= maxNonZeroIdx; i++) {
                    r = bigits[i] + r;
                }
                return r;
            } else {
                throw "unimplemented";
            }
        }

        // AF(this) = (nonNeg?1:-1) * Sum_i{ bigits[i] * base^i }
        private var nonNeg:Boolean;
        private var bigits:Vector.<uint>;

        public function BigNum(num:*=0) {
            nonNeg = true;
            bigits = new Vector.<uint>(1);
            if (num is uint && num < base) {
                bigits[0] = num;
            } else {
                this.parse(String(num));
            }
        }

        // modifies: this
        // effect: sets up this to match input (base 10).
        private function parse(input:String):void
        {
            if (false && base == 10) {
                parse_base10(input);
            } else {
                parse_general(input);
            }
        }

        // modifies: this
        // effect: same as parse(input)
        private function parse_base10(input:String):void
        {
            // This code *definitely* only works for base == 10

            bigits.length = input.length;
            for (var i=0; i < input.length; i++) {
                bigits[input.length - i - 1] = uint(input.charAt(i));
            }
        }

        // modifies: this
        // effect: same as parse(input)
        private function parse_general(input:String):void
        {
            // This code probably works for bases other than 10

            for (var i=0; i < input.length; i++) {
                var amount = uint(input.charAt(i));
                this.mulAndAddInPlace(10, amount);
            }
        }

        // modifies: this
        // effect: this := this*'scalar' + 'carry'
        private function mulAndAddInPlace(scalar:int, carry:int):void
        {
            for (var i=0; i < bigits.length; i++) {
                var a = bigits[i];
                a *= scalar;
                a += carry;
                bigits[i] = a % base;
                carry = (a - (a % base)) / base;
            }
            if (carry > 0) {
                bigits[bigits.length] = carry;
            }
        }

        // modifies: this
        // effect: this := this * 'base'
        private function leftShiftInPlace(amt:uint):void
        {
            for (var i=0; i<amt; i++) {
                bigits.unshift(0);
            }
        }

        private function bigit(idx:uint):uint
        {
            return (idx < bigits.length) ? bigits[idx] : 0;
        }

        public function add(that:BigNum):BigNum {
            // This code may or may not work for bases other than 10

            var r:BigNum = new BigNum;
            var len = Math.max(this.bigits.length, that.bigits.length);
            var carry = 0;
            for (var i=0; i<len; i++) {
                var b = this.bigit(i) + that.bigit(i) + carry;
                r.bigits[i] = b % base;
                carry = (b - (b % base)) / base;
            }
            if (carry > 0) {
                r.bigits[len] = carry;
            }
            return r;
        }

        private function clone():BigNum
        {
            return this.add(new BigNum);
        }

        public function mul(that:BigNum):BigNum {
            // This code may or may not work for bases other than 10

            // for now, multiply the same way you'd do it by hand:
            // by repeated multiply-by-scalar, shift, and sum.
            var accum:BigNum = new BigNum;
            for (var i=0; i<that.bigits.length; i++) {
                var scaled:BigNum = this.clone();
                scaled.mulAndAddInPlace(that.bigits[i], 0);
                scaled.leftShiftInPlace(i);
                accum = accum.add(scaled);
            }
            return accum;
        }
    }

}

Anyway, after the BigNum class done, I whipped up a Flash program that let me interactively input new seeds for such sequences. The first version was somewhat embarrassing, because I insisted on doing everything within the Actions block for the single frame of the SWF movie, rather than using any of the Flash Pro GUI to drag around UI elements.

But at least I had the good sense to factor out the middle square generation code. And then after I had that working acceptably, I was able to go back and experiment with using the Flash Pro GUI to use the built-in UI components more effectively (e.g. so that I could create a scrollable list for the output sequence rather than a non-scrollable label, and so that I could control the number of elements created in the sequence).

It is still not perfect; e.g. it would be better if the sequence were created on the fly in response to the user scrolling down the list. Then there would be no need to impose an a priori limit on the sequence length. But that would require a little bit more revision to the design than I want to undertake at the moment.

Anyway, here are the two versions, presented in three parts: first the middle square generation routine on its own, then the first ugly UI code, and then the better code that presumes that one has used Flash Pro to set up UI components in a sane manner.

Middle Square Generation

function middleSquareSequence(input:String, iters:uint):Vector.<String>
{
    var r:Vector.<String> = new Vector.<String>();
    if (isNaN(Number(input))) {
        r.push(input);
    } else {
        // Illustrate middle-square method for (bad) PRNG
        var digits:uint = input.length;

        // Make digit count even, to simplify definitionn of "middle digits"
        if ((digits % 2) == 1)
            digits = digits + 1;
        var dig2 = uint(digits/2);

        var bn:BigNum = new BigNum(input);
        var s:String = bn.toString();
        while (s.length < digits) {
            s = "0" + s;
        }
        r.push(s);

        for (var i=0; i < iters; i++) {
            var nsqr = bn.mul(bn); // this is <= 2*digits;
            // want the middle digits.
            // Ideally I'd do this via arithmetic, but I don't feel like
            // adding support for such to my hacked up BigNum class at the
            // moment.
            s = nsqr.toString();
            while (s.length < 2*digits) {
                s = "0"+s;
            }
            var sub:String = s.substring(dig2,2*digits-dig2);
            r.push(sub);
            bn = new BigNum(sub);
        }
    }
    return r;
}

Ugly Hacked Up UI Code

import fl.controls.Button;
import fl.controls.TextInput;
import fl.controls.List;
import fl.controls.Label;
import flash.events.MouseEvent;
import fl.controls.NumericStepper;

// ***************************************************************************
// Old hand written code below that did everything without using Flash Pro GUI
// (except for importing components into the SWF).  I.E., this code manually
// creates and positions the UI elements.  Its not really worth the pain for
// one-off scripts like this, especially now that I know how to get
// code-hinting for UI componets by explicitly redeclaring the variables.
// ***************************************************************************

if (true) {
    var b:Button;
    b = new Button;

    // Mutating b/textField doesn't seem to have
    // desirable effects.  The documentation just
    // says its a reference to the Button's internal
    // textfield, which makes me think that this never
    // should have been provided as a mutable property.
    // b.textField = t;

    b.label = "Click"
    // b.setStyle("textFormat", tf);
    // b.width = 400;
    // b.height = 300;
    b.x = 120;
    b.y = 10;
    addChild(b);

    var inp:TextInput;
    inp = new TextInput;
    inp.x = 120;
    inp.y = 40;
    inp.text = "5772156649";
    addChild(inp);

    b.addEventListener(MouseEvent.CLICK,
                       function() {
                           var seq:Vector.<String>;
                           seq = middleSquareSequence(inp.text, 400);
                           l.text = "";
                           for (var i=0; i<seq.length; i++) {
                               l.text += seq[i] + "\n";
                           }
                       });

    var l:Label;
    l = new Label;
    l.x = 220;
    l.y = 10;
    l.height = 400;
    if (true) {
        l.text = "Hi\nworld";
    } else if (false) {
        // (These are some tests of BigNum functionality
        //  I put in as I was getting this going.)
        l.text = (""+new BigNum("1234567890")
                  +"\n" + new BigNum("1234").add(new BigNum("1234"))
                  +"\n" + new BigNum("1234").add(new BigNum("1766"))
                  +"\n" + new BigNum("9999").add(new BigNum("1001"))
                  +"\n" + new BigNum("1000").mul(new BigNum("1000"))
                 );
    }
    l.selectable = true;
    addChild(l);
}

Nicer looking (and shorter) UI code presuming Flash Pro

import fl.controls.Button;
import fl.controls.TextInput;
import fl.controls.List;
import fl.controls.Label;
import flash.events.MouseEvent;
import fl.controls.NumericStepper;

// These are local variable declarations for the UI elements that I added
// manually in Flash Pro.  Apparently the tool is too stupid to know to provide
// code hinting unless I add these declarations (along with the above imports)
// myself.  (Or maybe this is a "feature" rather than a "bug")
var reseedButton:Button;
var seedInput:TextInput;
var outputList:List;
var numItersStepper:NumericStepper;

reseedButton.addEventListener(MouseEvent.CLICK,
  function () {
      outputList.removeAll();
      var seq : Vector.<String>;
      seq = middleSquareSequence(seedInput.text, numItersStepper.value);
      var seen = {};
      var seenRepeat:Boolean = false;
      for (var i=0; i<seq.length; i++) {
          if (seenRepeat || seq[i] in seen) {
              seenRepeat = true;
              outputList.addItem({label:(seq[i]+
                                         " (repeat)")});
          } else {
              outputList.addItem({label:seq[i]});
              seen[seq[i]] = true;
          }
      }
  });