Remix.run Logo
▲ itissid 3 hours ago

There is currently an effort underway to improve the bound. They have reached at a much larger kappa around 0.001635527380375392

https://github.com/CrocSwap/integer-mult-bounds

▲loufe 3 hours ago | parent [-]

I am astounded by the activity in this repo... what is going on? 508 PRs on 408 commits..? It's getting additions at a frenetic pace by a large number of contributors.

▲AnotherGoodName 3 hours ago | parent | next [-]

It’s unintentionally making a mockery of OpenAIs results by highlighting Blums speedup theorem in action. Namely that you can always reduce time complexity with a small move into space complexity.

That unintentional mockery of a repo is 262million lines of such moves and growing. I don’t think for a second anyone involved has a clue about complexity theory though or they’d just jump to the obvious “O(1) time complexity using an O(2^n) lookup table to cover all possible n bits of input” which is the final end state of Blums speedup theorem.

▲ 2 hours ago | parent [-]
[deleted]
▲ 3 hours ago | parent | prev [-]
[deleted]