## Problems Programming Math

Posted on October 17, 2008  Comments (2)

Arithmetic Is Hard – To Get Right by Mark Sofroniou

I’ve been working on arithmetic in Mathematica for more than 12 years. You might think that’s silly; after all, how hard can arithmetic be?

The standard “schoolbook” algorithms are pretty easy. But they’re inefficient and often unnecessarily inaccurate. So people like me have done a huge amount of work to find algorithms that are more efficient and accurate. And the problem is that these algorithms are inevitably more complicated, and one has to be very careful to avoid insidious bugs.

Take multiplying integers, for example. The standard “schoolbook” long-multiplication algorithm uses n^2 multiplications to multiply two n-digit numbers. But many of these multiplications are actually redundant, and we now know clever algorithms that take n^1.58, n log n, or even fewer multiplications for large n. So this means that if one wants to do a million-digit multiplication, Mathematica can do it in a fraction of a second using these algorithms–while it would take at least a few minutes using standard long multiplication.

It’s not easy to get reliable numerical computation, and it’s not something one can “bolt on” after the fact. It’s something one has to build in from the beginning, as we’ve done in Mathematica for nearly 20 years.

2 Responses to “Problems Programming Math”

1. Curious Cat Science and Engineering Blog » The Million Dollar Programming Prize
May 22nd, 2009 @ 10:36 am

The model may use 20 to 40 such factors to locate each movie and viewer in a multidimensional space…

2. Curious Cat Science and Engineering Blog » Dangerous Infinity
July 26th, 2009 @ 6:56 pm

[…] BBC Dangerous Knowledge web site – PoincarÃ© Conjecture – Problems Programming Math – Compounding is the Most Powerful Force in the Universe – Innovation with Math by curiouscat […]