Hacker News: nk_kolja

New comment by nk_kolja in "RSA-260 Factorized"

nk_kolja — Sat, 05 Sep 2026 11:51:31 +0000

Of course years. Typo.

New comment by nk_kolja in "RSA-260 Factorized"

nk_kolja — Fri, 04 Sep 2026 07:40:11 +0000

So RSA 260 is about 2-3 times harder than RSA 250, which was solved in 2700 core hours in 2020, so it’s probably no algorithmic improvements, just a tweak here and there plus faster hardware.

New comment by nk_kolja in "RSA-260 Factorized"

nk_kolja — Thu, 03 Sep 2026 16:32:28 +0000

Impressive. I wonder the methodology. Algorithmic improvements? More probably just an implementational optimisation. Last RSA record was due to special q sieving methods if I recall well, some 3k core hours. I hope there’s a theoretical improvement behind the result.

New comment by nk_kolja in "A complex structure on S^6 [pdf]"

nk_kolja — Mon, 24 Aug 2026 11:10:59 +0000

Reducing the problem to a quadratic form is pretty natural, and the paper from 2009 (though i see 2015) is quite an overkill. The result is a fairly standard consequence of the theory of representation by quadratic forms, and follows from Legendre's three square's theorem after some massaging. There's a good couple of centuries of foundations behind it.

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Fri, 21 Aug 2026 09:41:13 +0000

What a nice comment. Indeed, it feels like it was just waiting for you to find it.

That is a rather nice ritual, I think I will use it now to motivate myself to learn Scala.

New comment by nk_kolja in "A faster way to calculate the day of the week"

nk_kolja — Thu, 20 Aug 2026 11:58:29 +0000

Nice! And what a beautiful website!

Below the surface it's all the division with constant trick.

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 20:24:45 +0000

I doubt it would have unlooped itself from re-counting the steps in Program D and calculating the complexity of the algorithm. I couldn't get it to do it with a weeks worth of Claude pro, and in my experience once it's stuck it's stuck.

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 20:22:43 +0000

I'm happy to see someone commenting on Knuth's note. Don't worry, you probably won't need to correct anything unless you have a computer with an odd radix :)

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 20:22:12 +0000

It probably wouldn't help, and TAOCP from the beginning is too many pages. It would help to read the division algorithm chapter.

I introduce my own notation from medium->small division onwards. If it's any help u'', v'' are the limbs that the division instruction sees (the ones pertinent to qhat) and u',v' are all the lower limbs.

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 20:18:07 +0000

You are absolutely right. My mistake, the MIX computed the trial quotient in step 043 in a saturated way (which was enough to control the bug, thus my comment). It does indeed loop at step 62-64 (third edition book labels). I nevertheless stand my ground on the intention of Step D3.

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 19:54:59 +0000

What a lovely story

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 19:51:45 +0000

Thank you!

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 19:47:15 +0000

Thank you, i'm flattered!

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 19:36:08 +0000

Thank you!

Honestly, while waiting for the check I wondered what it would be, and 0x$1.00 feels just right. The name in the book came unexpectedly, it's really a reward on its own.

No bug in MIX, and there is no MMIX implementation yet. The transition of the first three volumes from MIX to MMIX is still far ahead. The MIX program actually implements Step D3 differently from what's written in Algorithm D, and this implementation, more aligned with 1st and 2nd editions of the book, avoids the error. The bug is due to a 1995 change in the trial quotient computation (that from my perspective came as part of a transition to MMIX). This broke correctness of Theorem B, which then led to overflows post Step D3 (in only one peculiar, rare, odd case).

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 19:18:33 +0000

Thank you! Indeed it's the infamous Step D3. In my opinion, with the new changes and the new Theorem B, this step will feel more natural, because it's essentially extending the 2/1 division into a 3/2 division.

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 19:17:13 +0000

I beg to differ.

A loop would also call for additional run-time analysis. And Knuth changed Step D3, if it were a loop he wouldn't have had to. Additionally, there is no loop in Program D, his implementation of Algorithm D in MIX.

If you read the whole chapter and not just the statement itself (though I'd argue the statement is enough), it's very clearly two if's.

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 13:48:33 +0000

Thank you for letting me now, but I cannot replicate the issue on Firefox. There are some issues with math and the animations not breaking on mobile, which I am working on repairing. (fixed)

EDIT: I have added a different fallback font so it should work on your Firefox now.

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Wed, 19 Aug 2026 13:44:10 +0000

It can still be cashed in, though not in any bank, you need to contact Knuth beforehand.

For me it will stay framed on the wall.

New comment by nk_kolja in "OpenLogi"

nk_kolja — Wed, 19 Aug 2026 11:32:51 +0000

I was looking forward to uninstalling that forsaken app.

New comment by nk_kolja in "A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)"

nk_kolja — Thu, 13 Aug 2026 14:11:27 +0000

I found a bug in Algorithm D, the long division algorithm in Knuth's "The Art of Computer Programming". It was discussed on HN a couple of times https://news.ycombinator.com/item?id=26562819 as well as on other websites. I sent a letter to Knuth and received a check and an annotated reply. The updated Theorem B, which was unchanged since 1969 is now dated 2026.

While searching for vulnerable implementations I also found a "bug" in llvm, so I expanded a bit on that too.