Hacker News new | past | comments | ask | show | jobs | submit login

There are clever techniques for doing multiplication like: Logarithm tables, prosthaphaeresis ("trigonometric logarithm tables"), quarter-square tables, abacuses. More recently (that is, within the last 60 years) faster than O(n^2) algorithms have been found as well, with a time complexity of O(n log n) having been achieved. These last algorithms range from being impractical to do by hand, to being outright galactic.



I was just about to post this. Arithmetic starts going to the moon once you're dealing with larger than 64-bit numbers. Stuff like Karatsuba's algorithm or you can read all the fourier transform convolution hacks libraries like mpdecimal use. Arithmetic is also very dominant in any sort of low-level programming. It's just that it isn't the same kind of arithmetic that math is used to dealing with, or even likes dealing with, since it's usually over a field that mixes boolean logic with arithmetic. It actually ended up being a security issue because malware authors would find ways to obfuscate their programs using types of math that haven't traditionally been studied, so math tools would be completely powerless to make sense of them. So definitely not a solved problem.


I didn't know about prosthaphaeresis! Thank you!

Richard Guy developed a single-scale nomogram based on elliptic curves in 01953: https://www.jstor.org/stable/3609499

His explanation is wonderfully simple; quoting the beginning: "Since the equation x³ + ax + b = 0 has zero for the sum of its roots, the x-coordinates of the three intersections of the line y = mx + c and the curve y = x³ + px + q add to zero." It may be entertaining to attempt to derive the rest of the nomogram from that sentence and the use of logarithms before consulting the (one-page) paper.

A nice advantage of Guy's contrivance over slide rules is its facility with squares and square roots. On a conventional Oughtred slide rule you can easily enough read off the square root of a number on the A or B scales by reading across the hairline to the D or C scales, respectively; but if your square had been computed on C or D, you are out of luck. Guy's nomogram has some similar limitations, but you can in general easily take the square root of any point on it.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: