4 ms·

Euclid's GCD algorithm, and Russian peasant multiplication.

• toolslive 8y ago
  I never heard about "Russian peasant multiplication" before. When I read it, I thought you were referring to Karatsuba multiplication. As it turns out, you didn't. http://mathforum.org/dr.math/faq/faq.peasant.html http://mathforum.org/dr.math/faq/faq.peasant.html https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm
  • meuk 8y ago
    Yup. Applying Russian multiplication to matrices is surprisingly effective for evaluating recursive relations (it can evaluate the nth Fibonacci number in O(log n)) Karatsuba is also a nice 'proof-of-concept' algorithm (it shows that it is possible to do better than O(n^2) at multiplication in the simplest way possible) that's also very practical - and it has a nice anecdote behind it :)
• yesenadam 8y ago
  I like this version of the Euclid algorithm: Make a rectangle with side lengths of 2 positive real numbers. Put the biggest square inside (i.e. against a short side) that you can, add as many as fit. If there's still a gap, put the biggest square that fits in that, repeating until filled.. If you never fill the gap, the ratio is irrational. The number of squares of each size used gives the ratio's continued fraction.
  • undershirt 8y ago
    in visual form (hold shift and move mouse): https://shaunlebron.github.io/ratios/ https://shaunlebron.github.io/ratios/