In the last post, I gave an overview of how BigIntegers are stored and how addition and subtraction work. Now it's time to move up the hyperoperation sequence and and discuss multiplication.
Probably the simplest way to think about multiplication is repeated addition. In other words, 4*5
In the last post, I gave an overview of how BigIntegers are stored and how addition and subtraction work. Now it's time to move up the hyperoperation sequence and and discuss multiplication.
Probably the simplest way to think about multiplication is repeated addition. In other words, 4*5 = 5+5+5+5
. Using that definition, it would be trivial to write a multiplication function in terms of addition:
// Assume we've defined "ZERO" and "ONE" constants and a "notZero(n)" function, which are all trivial.
// notZero can be as simple as "return n.sign !== 0".
function multiply(a, b) {
var product = ZERO;
while (notZero(a)) {
product = add(product, b);
a = subtract(a, ONE);
}
return product;
}
Something like the code above would work, but would be extremely slow. Imagine multiplying even relatively small numbers (for a big integer library) like 123,456,789 * 65,128,321. Even optimizing it by making sure a is smaller (remember, order doesn't matter in multiplication) we would have to run the loop 65,128,321 times, with an addition and subtraction each time. Now imagine two 100 digit numbers! Obviously this won't work.
The key thing to remember is that numbers are polynomials. So 123 * 456
is really (1 * 100 + 2 * 10 + 3) * (4 * 100 + 5 * 10 + 6)
. Simplifying a little more, we get (100 + 20 + 3) * (400 + 50 + 6)
. Lets leave the right side how it is and add up the terms on the left to get our original 123 back: 123 * (400 + 50 + 6)
. Now we can use the distributive property and get 123400 + 12350 + 123*6 = 49200 + 6150 + 738
.
All that is a great flashback to your high school algebra class, but how does it help us? Remember that to multiply by a factor of 10, you just add zeros to the end of the number. If we factor out the power of 10 from each term, we just have to do a couple single-digit multiplications, append some zeros, and do a couple additions. Easy! In fact, this is how you've been doing multiplication since grade school.
123
x 456
56088
So let's break down what we're doing. Starting from the right, take each digit from the bottom number, multiply it by each digit of the top number (also from right to left) and write down the result. I've glossed over it so far, but remember if you end up with a two digit number, you have to carry the first digit and add it to the next result. Then you move to the next digit, remembering to "multiply by 10" by shifting the numbers over to the left each time. Finally, add up all the "partial products" and you have the (hopefully correct) answer!
So, how do we do this in code? I'm glad you asked. Here's a straightforward implementation (we'll optimize it slightly by eliminating some of the intermediate steps later):
function multiply(a, b) {
// To keep track of all the partial products
var partialProducts = [];
// For each digit of b
for (var i = 0; i < b.digits.length; i++) {
var carry = 0;
var digit;
var partial = {sign: 1, digits: []}; // Initialize a new partial product
// For each digit of a
for (var 0; j < a.digits.length; j++) {
digit = (b.digits[i] * a.digits[j]) + carry; // Multiply the digits, adding in any carry
carry = Math.floor(digit / 10); // Integer divide by 10 to get the first digit
partial.digits[j] = digit % 10; // Mod 10 gets the second digit
}
// Don't forget the final carry (if necessary)!
if (carry > 0) {
partial.digits[j] = carry;
}
// Shift the digits to the left to multiply by the next power of 10
for (var shift = 0; shift < i; shift++) {
// Unfortunately, JS's naming is backwards from ours.
// "array.unshift(0)" pushes a zero into the front of the array, which is what we want
partial.digits.unshift(0);
}
// Append this partial product to the list
partialProducts.push(partial);
}
// Now add up all the partial products
var product = ZERO;
for (var i = 0; i < partialProducts.length; i++) {
product = add(product, partialProducts[i]);
}
return product;
}
Whew! That's pretty long, but fairly simple. For each digit of b, loop through each digit of a, multiplying the digits and storing them in the partial product, then add up the partial products at the end.
It's also still inefficient for several reasons. It's much better than the simple "loop and add" function at the beginning but we can do better, and actually shorten the code at the same time.
The problem is all those partial products. Instead of building up a list (taking up a potentially large amount of memory) then adding them up at the end, we can just add in each product as we go. We can also avoid pushing all the zeros in by adjusting how we index into the arrays.
function multiply(a, b) {
var partial = { sign: a.sign * b.sign, digits: [] }; // digits should be filled with zeros
// For each digit of b
for (var i = 0; i < b.digits.length; i++) {
var carry = 0;
var digit;
// For each digit of a
for (var j = i; j < a.digits.length + i; j++) {
// Multiply the digits, and add them to the current partial product, along with any carry
digit = partial.digits[j] + (b.digits[i] * a.digits[j - i]) + carry;
carry = Math.floor(digit / 10); // New carry
partial.digits[j] = digit % 10; // Put the result back into the partial product
}
// Don't forget the final carry (if necessary)!
if (carry) {
digit = partial.digits[j] + carry;
carry = Math.floor(digit / 10);
partial.digits[j] = digit % 10;
}
}
// That's it!
return partial;
}
I didn't mention it before, but the nice thing about multiplication is that the sign is easy to get right. Because our sign
property is a 1 (or zero) with the same sign as the number itself, the resulting sign is just a.sign * b.sign
.
The last function above, is basically how the BigInteger library does multiplication (except in base 10000000 and, as usual, I've skipped over some minor details for clarity). But there are actually more sophisticated algorithms to make multiplying huge numbers faster.
They are mostly based on Karatsuba multiplication, which is a recursive "divide and conquer" algorithm. The added complexity and overhead of recursive function calls makes it slower for "reasonably sized" numbers, so it's best to use simple long multiplication until you get to some threshold then switch to Karatsuba multiplication. I experimented with supporting it early on and the cutoff was somewhere in the several-thousand-digit range.
]]>The Chrome Scientific Calculator supports "approximate" and "exact" numbers. As a slightly simplified explanation, approximate numbers are represented by native JavaScript floating point numbers. Exact integers are represented by an arbitrary-precision BigInteger class (rational numbers have two BigIntegers for the numerator and denominator).
So how do
]]>The Chrome Scientific Calculator supports "approximate" and "exact" numbers. As a slightly simplified explanation, approximate numbers are represented by native JavaScript floating point numbers. Exact integers are represented by an arbitrary-precision BigInteger class (rational numbers have two BigIntegers for the numerator and denominator).
So how do you do math on arbitrarily large integers in a language that only supports 64-bit floating point numbers? Basically the same way you do math in 3rd grade.
A BigInteger is just a sign and an array of digits, from the least significant to most significant:
// n = -123
var n = {
sign: -1,
digits: [3, 2, 1]
};
The digits look backwards, but by storing the digits with the ones place first, they will line up with other numbers correctly even if they have different lengths. The sign can be any of {-1, 0, 1} to represent negative, zero, and positive respectively. In mathematical terms (abbreviating digits to "d"):
If you look at the source, you'll probably notice that I'm actually using base 10000000, not base 10. I'm using decimal in these examples because it makes things clearer but everything works pretty much exactly the same way in any base. Using a larger base just makes things more efficient because you get 7 digits in each array entry. The examples below are also simplified for demonstration purposes, and don't handle things like signs and different-sized numbers. Keep in mind too that sign
and digits
are abbreviated to _s
and _d
to save a few bytes in the .js file.
OK, so that's simple enough, but what about operators like addition, subtraction, multiplication, and division? They are pretty much exactly how you would do it by hand. I'll go through each of them and show how they work. I'll cover addition and subtraction, then multiplication and division in later posts.
Here's how would you add two numbers by hand:
314159
+ 2718
-------
316877
You stack them up with the ones place lined up. Then you go from right to left, adding each pair of digits. 8+9 = 17, 5+1 = 6, 1+7 = 8, and so on. But the 17 is a problem, because you can only put down one digit in each place, so you have to carry the 1 to the next place. So backing up, we have 9+8 = 17, so write down the 7 and carry the one, then 5+1+1 = 7. That's one digit so we don't have to carry anything, so we just have 1+7 = 8 and so on. Pretty simple right? It's exactly what you've been doing since first grade (or whenever).
So how would you do that in JavaScript? Remember we're storing the digits "backwards" so digits[0] is the right-most/least significant digit. That means the places are already lined up correctly, so we can just loop through them, adding each pair, and keeping track of the carry. For simplicity, I'll assume that both numbers are positive and we padded the digit arrays with zeros to be the same length. In the actual implementation, any extra digits in one number are handled separately to make it faster.
var c = { sign: 1, digits: [] }; // We'll store the result in c
var carry = 0; // Nothing to carry yet
for (var i = 0; i < a.digits.length; i++) {
c.digits[i] = a.digits[i] + b.digits[i] + carry;
if (c.digits[i] >= 10) { // Oops, too big.
carry = 1; // Set the carry to be added into the next digit
c.digits[i] -= 10; // Adjust to be one digit
}
else {
carry = 0; // It fit, so there's nothing to carry
}
}
if (carry) { // Don't forget to add the final carry if it's needed
c.digits[i] = carry;
}
Instead of the if (c.digits[i] < 10) {...
statement, we can use the remainder and (integer) division operators:
c.digits[i] = (a.digits[i] + b.digits[i] + carry) % 10;
carry = Math.floor((a.digits[i] + b.digits[i] + carry) / 10);
Since JavaScript numbers are always floating point, we have to use Math.floor
to fake integer division.
Subtraction is basically the exact opposite of addition. You loop through each digit and subtract. If the result is negative, borrow a 10 from the next digit. Again, for simplicity we'll assume the numbers are positive, padded to be the same length, and that a > b (if it's not, we can force it by playing with the signs).
var c = { sign: 1, digits: [] }; // We'll store the result in c
var borrow = 0; // We didn't borrow anything yet
for (var i = 0; i < a.digits.length; i++) {
c.digits[i] = a.digits[i] - b.digits[i] - borrow;
if (c.digits[i] < 10) { // Oops, we can't have a negative digit
borrow = 1; // We'll borrow 10 from the next pair of digits
c.digits[i] += 10; // Add the borrowed 10
}
else {
borrow = 0; // We don't need to borrow anything
}
}
// We made sure a < b to make sure we never have to borrow after the last digit, so we're done
With the combination of addition and subtraction, we can handle adding any combination of positive and negative numbers (e.g. to subtract a negative from a positive, pretend both are positive and add them).
In part 2, I'll cover the multiplication algorithm. Division will come in a later post.
]]>A few days ago, I launched a service for the Scientific Calculator app that lets you save and load scripts online and share them with other people. Once you have an account (using your Google account naturally), you can see your own scripts and load them directly from the library
]]>A few days ago, I launched a service for the Scientific Calculator app that lets you save and load scripts online and share them with other people. Once you have an account (using your Google account naturally), you can see your own scripts and load them directly from the library dialog in the calculator.
You can also view other people's libraries online at www.calclibrary.com. At the moment, it's just some examples I uploaded, but I'm hoping it will end up being a useful resource for extending the functionality of the calculator and for learning from other people's code. Especially since I haven't gotten around to writing any tutorials or overviews of the language, other than the reference-type documentation that comes with it.
There's also a secret way to use the calculator online without installing the Chrome app. There are no links to it at the moment, but it shouldn't be too hard to find if you look for it. It should even work in other modern browsers, although I haven't tested it much outside of Chrome. Once I've tested it more in other browsers, I'll probably link to it and make it "official".
]]>About a month ago I published a scientific calculator app to the Chrome Web Store (and I'm just now getting around to blogging about it).
I was thinking about Chromebooks one day, and realized there was no way I could use one without a good scientific calculator. So I checked
]]>About a month ago I published a scientific calculator app to the Chrome Web Store (and I'm just now getting around to blogging about it).
I was thinking about Chromebooks one day, and realized there was no way I could use one without a good scientific calculator. So I checked the Web Store, and didn't like any of the existing ones. The best one I could find was the appropriately-named "Calculator" (or "C∞lculator"), but it appears to only be extendable with JavaScript, not it's own expression syntax. Most of the others were either way too basic or used Google and Wolfram|Alpha to do their calculations.
So after much a few minutes of thought, I decided to write my own. I already had a functional programming language I was working on (in JavaScript), so it didn't take long to get the basic language working.
The (unnamed) language is pretty simple, and still needs a few additions, but it works. It's a functional language where everything is an expression. It's mostly what you would expect from a calculator but has a few things that are kind of interesting.
Here's the download link again, if you want to try it. You'll need Google Chrome to run it for now, but eventually I'll probably make an online version that works in other browsers.
Like Mathematica, you can create lazily-evaluated variables with the :=
operator. For example:
y := x^2
(x doesn't have to be defined yet)
= true
(always returns true, since we can't evaluate it yet)
x = 4
= 4
y
= 16
x = sqrt 2
= 1.4142135623730951
y
= 2.
(whoa)
It basically creates a function that automatically calls itself whenever you need it. It even closes over the current scope. Here's a more complex example:
var counter
(put counter in scope but don't define it yet)
= undefined
(function() { var current = 0; counter := (current += 1) })()
(just like javascript, this is a way to hide "current" in a private scope)
= true
counter
= 1
counter
= 2
counter * 2
= 6
Most operators can be converted into functions by prefixing them with a "special" colon operator. For example, :+(1, 2, 3)
is equivalent to 1 + 2 + 3
. The :
operator can also take a literal (:42
, which gives you a function that always returns 42) or a variable name (:x
, returns x).
There are some interesting non-obvious applications, like :()
as a shortcut for the identity function. Or there's this: adder = :function(y) { x + y }
. When applied to a function, the new function created by the :
operator implicitly takes an argument, x. Since functions close over the current scope (including their arguments), adder takes x
and returns a function that adds it's argument (y) to x. Here's an example of how it would be used:
adder = :function(y) { x + y }
= function(x) {function(y) {(x + y)}}
add1 = adder(1)
= function(y) {(x + y)}
add2 = adder(2)
= function(y) {(x + y)}
add1(4)
= 5
add2(4)
= 6
A more common application would be passing operators as arguments to functions like map or reduce:
map(:sqrt, [1, 4, 9])
= [1, 2, 3]
Note that sqrt is an operator (along with sin, cos, ln, etc. basically the standard unary functions) so it needs to be converted to a function.
There's still a lot that I want to do with it, like a way to save and share libraries of functions with other users, big decimals instead of 64-bit floating point numbers (big integers and fractions are already supported), symbolic math (i.e. a CAS), lots more built-in functions and constants, units, etc. I'm open to other ideas and feedback, so let me know if there's anything you want to see added or improved.
]]>Multiplayer is still in beta, but I've moved it to the main site, so everyone gets the other improvements. I think I'm pretty close to removing the "beta" label, but I want to get some more games in just to make sure everything works correctly. So find some
]]>Multiplayer is still in beta, but I've moved it to the main site, so everyone gets the other improvements. I think I'm pretty close to removing the "beta" label, but I want to get some more games in just to make sure everything works correctly. So find some friends to play with! As always, I welcome any feedback, criticism, questions, ideas, etc.
Here are some of the improvements since last time:
There have been lots of changes so far for multiplayer games. Besides various minor bug fixes and improvements, I've implemented several new features:
There have been lots of changes so far for multiplayer games. Besides various minor bug fixes and improvements, I've implemented several new features:
The most commonly requested feature for Yahtzee is multiplayer support (seriously, like... three people have asked for it). Being the accommodating guy that I am, I've been slaving away at working on it once in awhile for the last week or so, and it's about ready to be released as
The most commonly requested feature for Yahtzee is multiplayer support (seriously, like... three people have asked for it). Being the accommodating guy that I am, I've been slaving away at working on it once in awhile for the last week or so, and it's about ready to be released as a beta.
Before I get into what's new and what's coming, here's the link: http://multiplayer.silent-matt.appspot.com/multiplayer/create.
Remember this is still a beta, so you'll probably find bugs, and it may change often or completely disappear.
It should be pretty simple to get started. If it's confusing, please let me know so I can improve the process for other people. The link above, should take you directly to a page where you can choose a password, or just click "Create Game" to let the game pick one for you. If you're not logged in (you won't be the first time) you will need to sign in with your normal Google account or OpenID (you need a profile for multiplayer... see below).
Once you choose a password and click "Create Game", you'll see a page with a link to share with whoever you want to play with and a reminder of your password. For now, you'll need to send it via email, IM, carrier pigeon, etc. When your friend goes to the link (and signs in), they will see a page similar to yours, and they'll show up in the player list. Once enough people have joined the game, click "Start Game". Only the player who created the game can start it.
After you start the game, you'll see the normal Yahtzee page, plus a list of players and scores across the top. The player whose turn it is should be highlighted. You can hover your mouse over a player's name to see their score card at any time. That will also show a popup where you can go to their profile page or (after around 30 seconds with no activity) nudge them to get them going. Be nice though, because if they still don't do anything, they'll be kicked out of the game so you can continue without them.
I've had a lot of fun working on the new Yahtzee version, and it's finally at a point where I feel like it's ready to leave the beta stage and completely replace the old one. If you haven't paid attention to the blog (let's be honest here; you haven't), here's
]]>I've had a lot of fun working on the new Yahtzee version, and it's finally at a point where I feel like it's ready to leave the beta stage and completely replace the old one. If you haven't paid attention to the blog (let's be honest here; you haven't), here's what's new:
New design. Since it's running on a different subdomain (and completely different back end... see below) and the old version never really looked right stuffed into my website's layout, I decided to start over with a new look. To me at least, it looks much nicer.
Personal statistics. I've been keeping track of (almost) every game played in the current version and generating charts and averages, but I've always wondered how I compared to everyone else. If you have too, you can now sign in with either a Google account or OpenID. You'll be able to see your own average score and histograms.
Bug fixes. I've finally fixed some small bugs and annoyances that have been bugging me for awhile and I've been meaning to get around to.
Completely new back-end code. I've completely rewritten the server-side part of the game on Google's App Engine in JavaScript (yes, you read that right). Specifically, I'm using the RingoJS framework and AppengineJS running on Rhino. Why? The whole reason for writing the game in the first place was the play around with JavaScript, so I decided to extend that to the server-side portion of the code, and so far it's been a lot of fun.
Just because it's not in beta anymore, doesn't mean there won't still be issues, so if you find anything, be sure to let me know (there's a feedback link at the bottom of the page). I'm also still working on some new features and improvements for the future.
]]>As promised, I'm getting ready to launch a new version of Yahtzee with personalized statistics and a new design. I'm still working on some new features and I haven't tested it well in anything other than Google Chrome (my preferred browser and by far the most popular in this case)
]]>As promised, I'm getting ready to launch a new version of Yahtzee with personalized statistics and a new design. I'm still working on some new features and I haven't tested it well in anything other than Google Chrome (my preferred browser and by far the most popular in this case), so I'm sure there are still issues, so I'm calling it a public beta right now.
You can check it out at yahtzee.silentmatt.com/yahtzee. Let me know if you run into any problems (be sure to let me know what browser version you're using) or have any ideas for improvements. You can play "anonymously" but if you want to keep track of your own statistics, click the "sign in" link to create an account. You can sign in with a Google account or OpenID.
Note that any games you play in the current version are automatically imported into the new version, but they won't be counted toward your personal statistics. Also, games played in the new version don't get counted in the old one. The mobile version doesn't let you sign in or view your stats yet (or any stats for that matter), but if you are signed in from the "full version", the games will still be associated with your account.
]]>So the 20,000th Yahtzee score was submitted today. What's interesting is that the I've been keeping statistics for the last four years, but 10% of those are from this week. That means it took over four years to get to 18,000, and one week to get another 2,
]]>So the 20,000th Yahtzee score was submitted today. What's interesting is that the I've been keeping statistics for the last four years, but 10% of those are from this week. That means it took over four years to get to 18,000, and one week to get another 2,000!
So what made the difference? I'm glad you asked. About a week ago Google launched the Chrome Web Store where, just for fun, I added a Yahtzee "app" for Google Chrome. Here's a graph of the number of games played per day for the last month:
I have no idea if the current level of traffic will continue, or if it will go back down to normal, but it's been interesting to see the short-term effect at least.
Just before the Web Store launch, I added a few new features. Most significantly, there's the new mobile version (really only tested on Android).
There's also an "undo" button so if you click on the wrong spot by mistake, you're not stuck with it. You can't undo once you roll though, so be careful.
A small change that had been bugging me is the animated dice when you roll. The biggest reason for that (other than because it looks cool) is to prevent accidental double-rolls. Another reason is that once in awhile when you roll, it looks like nothing changes because you rolled the same dice. Now it's obvious that you really did click (or tap) roll.
There were also lots of changes "under the hood" to support the mobile interface and undo, as well as just generally making it more "elegant". The code is looking less and less like I threw it together in a couple nights.
I've been planning on adding personalized statistics, so you can log in and keep track of your personal best scores, averages, etc. I don't have a timetable for when that will be ready, because I'm experimenting with some different technologies.
I may add a multiplayer option, but I haven't decided how that would work yet. Multiplayer Yahtzee is still (mostly) a solitaire game where the players take turns rolling, but it could still be fun to set up a game and see who gets the highest score.
]]>