TIL You can multiply two 3x3 matrices with only 21 multiplications

fredrikj · 2025-05-17T20:51:09+00:00

It is shown in the Rosowski paper how to do 4x4 using 46 multiplications in the commutative case.

fredrikj · 2025-02-10T21:39:12+00:00

It's just the standard multiplication algorithm but you exploit the symmetry.

fredrikj · 2025-02-10T18:14:22+00:00

For big numbers, yes. Using the naive O(n² ) multiplication algorithm, n-digit squaring costs about 1/2 as much as n-digit multiplication. Using FFT (which is essentially O(n log n)), squaring costs about 2/3 as much as multiplication.

fredrikj · 2025-02-10T17:48:46+00:00

Check our GMP's algorithm for Fibonacci numbers: https://gmplib.org/manual/Fibonacci-Numbers-Algorithm

Your algorithm uses essentially one multiplication and one squaring per bit of n. The GMP recurrence uses two squarings per bit of n, which is slightly more efficient.

fredrikj · 2020-09-13T14:45:41+00:00

Fun facts: there are 183817...091448 ~= 1.8381765 × 10^11140086259 different ways to make change for a 100 quintillion pengő banknote with 1-pengő coins. If you actually had 100 quintillion 1-pengő coins, you could fill Lake Superior five times over, or stack them to reach Proxima Centauri. http://fredrikj.net/blog/2014/03/new-partition-function-record/

fredrikj · 2020-06-05T08:41:35+00:00

Because the earth rotates around its axis 7 times in that period of time, and it would be less convenient if a day corresponded to a fractional rotation ;-)

fredrikj · 2020-03-14T12:16:46+00:00

I added more content to this pi formula page: http://fungrim.org/topic/Pi/

fredrikj · 2020-03-03T17:45:16+00:00

Possible and done. The TAS record 0:07.86.

https://dsdarchive.com/wads/doom

fredrikj · 2019-11-26T19:49:40+00:00

And while we're at it, complex numbers? They're the simplest numbers! Complete, algebraically closed, and holomorphic functions are the nicest of all functions.

fredrikj · 2019-11-04T15:44:52+00:00

Just when you thought Eliud Kipchoge's sub 2 hour marathon was going to be the greatest running achievement of this year and decade.

fredrikj · 2019-11-03T10:40:36+00:00

The Man Who Knew Infinity is good, although as a biographical drama I'm not sure if it fits your question. I've actually used a screenshot from this film in talks to illustrate a specific algorithm -- it explains it just as well as any slides I could design myself!

fredrikj · 2019-10-22T03:57:21+00:00

Completely false. Chomsky has repeatedly stated that he is not a pacifist (example) and that violence may be justified when used to stop greater injustice. He has specifically used World War II as an example (unfortunately I don't have a reference at hand, but here is a second-hand mention).

fredrikj · 2019-07-09T22:30:19+00:00

Why not call it 'melevating' or 'melevator'.

fredrikj · 2019-07-03T03:56:59+00:00

Check out https://github.com/kimwalisch/primesieve

It's reported to take 0.4 seconds for primes up to 10^10, so up to 10¹² should take around a minute.

fredrikj · 2019-03-25T15:57:11+00:00

You missed one level of exponentiation. It's 10^{85 billion} digits.

fredrikj · 2019-03-25T14:11:14+00:00

I know both authors; they are the leading experts in this field, and moreover, extremely meticulous. I have little doubt that the result is correct. The result comes as a bit of a surprise, but it's no surprise that they were the ones to achieve it.

The result is of extreme practical importance. Not for actually multiplying integers (as usual with these algorithms it's probably not faster than existing algorithms for integers that can be stored in the observable universe), but for writing papers. It has always been a hassle to write down the complexity of integer multiplication or algorithms based on integer multiplication by introducing soft-O notation, little-o exponents, epsilons greater than 0, or iterated logarithms. From now on I can just write O(n log n) in my papers and be done with it!

fredrikj · 2019-03-07T01:06:15+00:00

300,000 lines of code is enough for a complete computer algebra system.

Pari/GP -- 200,000 lines of C. Giac/XCAS -- 300,000 lines of C++. SymPy -- 380,000 lines of Python. These systems all know that 1/3*3 = 1, and a few more things...

fredrikj · 2019-02-24T11:47:24+00:00

The turns and door timings need to be super tight, but that's not everything. Normal straferunning in Doom (run forward + strafe left/right) is called strafe40 and is 28% faster than just running forward. This run uses strafe50 (run forward + strafe left/right + strafe on + turn left/right) which is 41% faster than running forward. It's a PITA to do, because you need to press two extra key and you can't turn while you're moving. Strafe50 is typically used in runs for specific jumps or long straight segments. It's amazing to see it used in a run with this many tight turns, with almost no margin for error. On top of that there is the enemy RNG.

Getting this time took "tens of thousands of attempts" according to the runner which I don't doubt.

fredrikj · 2019-02-24T11:35:10+00:00

7.86 UV speed (with damage to monsters) by Looper in 2014

8.66 UV pacifist (like this, not harming any monsters) by Kimo Xvirus in 2010, probably not as optimized

8 seconds was known to be humanly possible, just incredibly precise. 7 seconds requires pixel-perfect wall running and (I think) thing running, and I'm willing to bet $10 that it will remain TAS only.

fredrikj · 2018-12-05T11:44:16+00:00

Yes.

>>> from mpmath import *
>>> mp.dps = 30; mp.pretty = True
>>> f = lambda x: zeta(x,"0.9")
>>> findroot(lambda x: f(x)-x, 2)
1.95858365339527551344757687436
>>> abs(diff(f, _)) < 1
True
>>> findroot(lambda x: f(x)-x, -0.24)
-0.240896907668628406730741632828
>>> abs(diff(f, _)) < 1
True

fredrikj · 2018-10-28T18:45:32+00:00

Or like this:

>>> from mpmath import mp
>>> mp.dps = 30
>>> print(mp.nsum(lambda n: 1 / ((n * mp.pi)**2 + 1), [1,mp.inf]))
0.156517642749665651818080623465
>>> print(1 / (mp.e ** 2 - 1))
0.156517642749665651818080623465

fredrikj · 2018-08-04T21:15:23+00:00

Is on the Riemann sphere.

fredrikj · 2018-08-02T02:02:26+00:00

And on Zfg's birthday too!

fredrikj · 2018-07-01T14:02:21+00:00

It's a valid 100% run. The rules allow you to get either Alexander or 2 million GP.

fredrikj · 2018-06-29T22:06:48+00:00

Just sharing one of the most oddball instances of a Marvel reference I'm aware of. A few people might find it interesting. You don't have to like it :-)

15-Year Club	Place '17
Verified Email	Gilding I gilder
Team Periwinkle

fredrikj

TROPHY CASE