News for hackers. Stuff that matters.
Re:Did any processor implement an integer square root instru... by WithinReason on Sunday April 07, 2024 @08:41AM (#39960352)
Sounds like it's possible to run any algorithm in the world in 1 clock cycle.
Re:Did any processor implement an integer square root instru... by retrac on Sunday April 07, 2024 @11:40AM (#39961490)
Yes. In theory, any pure function can be turned into a lookup table. And any lookup table that isn't just random numbers can be turned into a more compact algorithm that spends compute to save space.

Such tables may be infeasible, though. While a int8 -> int8 table only needs 256 bytes, an int32 -> int32 needs 16 gigabytes.

Re:Did any processor implement an integer square root instru... by DaiPlusPlus on Sunday April 07, 2024 @01:20PM (#39962202)
Fractal functions are pure, but don’t lend themselves well to memoization nor lookup tables.
Re:Did any processor implement an integer square root instru... by meindnoch on Monday April 08, 2024 @09:49AM (#39969701)
What does this statement even mean? Every function from a finite domain is just a lookup table, period.
Re:Did any processor implement an integer square root instru... by DaiPlusPlus on Monday April 08, 2024 @12:32PM (#39971357)
Who said anything about finite-domains?
Re:Did any processor implement an integer square root instru... by meindnoch on Tuesday April 09, 2024 @09:55AM (#39979471)
Every function has finite domain on a computer.
Re:Did any processor implement an integer square root instru... by DaiPlusPlus on Tuesday April 09, 2024 @01:54PM (#39982144)
Arbitrary-precision real-number libraries would disagree with you there.
Re:Did any processor implement an integer square root instru... by meindnoch on Wednesday April 10, 2024 @06:15AM (#39989008)
False. A computer always has a finite amount of memory.
Re:Did any processor implement an integer square root instru... by ajb on Sunday April 07, 2024 @08:57AM (#39960449)
It isn't, because eventually the size of your logic or table becomes larger than the distance a signal can propagate in one clock tick. Before that, it likely presents practical issues (eg, is it worth dedicating that much silicon)
Re:Did any processor implement an integer square root instru... by willcipriano on Sunday April 07, 2024 @11:37AM (#39961464)
Have slower ticks. A planet size CPU that runs at .5 hz but can work on impossibly large numbers.
Re:Did any processor implement an integer square root instru... by volemo on Sunday April 07, 2024 @12:07PM (#39961658)
And 27.7% [1] of the planet's crust is silicon already!

[1] Britannica: Silicon

Re:Did any processor implement an integer square root instru... by gameshot911 on Sunday April 07, 2024 @11:41AM (#39961493)
That's actually a really fascinating science fiction idea!
Re:Did any processor implement an integer square root instru... by willcipriano on Sunday April 07, 2024 @11:58AM (#39961594)
It's sort of the plot of the Douglas Adam's books.

https://hitchhikers.fandom.com/wiki/Earth

Re:Did any processor implement an integer square root instru... by com2kid on Sunday April 07, 2024 @02:38PM (#39962740)
https://en.wikipedia.org/wiki/Matrioshka_brain

:-D

It's a topic that has been explored quite a bit in science fiction literature.

Re:Did any processor implement an integer square root instru... by karmakaze on Sunday April 07, 2024 @03:22PM (#39963070)
Related to the fallacy of comparing what's slow in our world with what's computable in a simulation of it--there's no requirement for time to tick similarly.
Re:Did any processor implement an integer square root instru... by Dylan16807 on Sunday April 07, 2024 @07:43PM (#39964917)
> Have slower ticks.

Yes, this solves the stated issue about huge lookup tables.

> A planet size CPU that runs at .5 hz but can work on impossibly large numbers.

This doesn't make much sense to me, though.

If your goal is "any algorithm", you'll often have to go a lot slower than .5Hz. A hash-calculating circuit that's built out of a single mountain of silicon could have a critical path that's light-years long.

But if your goal is just "work on impossibly large numbers", but it's okay to take multiple ticks, then there's no reason to drag the frequency down that low. You can run a planet-scale CPU at 1GHz. CPUs have no need for signals to go all the way across inside a single tick.

Re:Did any processor implement an integer square root instru... by Vecr on Monday April 08, 2024 @12:00AM (#39966092)
You'd need way better clocks and synchronization circuits than exist now though, but I don't see any pure physical barriers.
Re:Did any processor implement an integer square root instru... by Dylan16807 on Monday April 08, 2024 @12:28AM (#39966209)
The whole thing doesn't need to be on the same clock domain. You can put clock crossings every inch.
Re:Did any processor implement an integer square root instru... by brudgers on Monday April 08, 2024 @07:40AM (#39968675)
impossibly large numbers

Forty-two for example?

Re:Did any processor implement an integer square root instru... by rcxdude on Sunday April 07, 2024 @09:16AM (#39960560)
With a sufficiently large chip and a sufficiently slow clock, sure.
Re:Did any processor implement an integer square root instru... by wheybags on Sunday April 07, 2024 @09:26AM (#39960606)
"Give me a lut large enough and an infinite period of time to execute, and I shall simulate the world"
Re:Did any processor implement an integer square root instru... by dartos on Sunday April 07, 2024 @11:20AM (#39961343)
“Every cycle”
Re:Did any processor implement an integer square root instru... by robinduckett on Sunday April 07, 2024 @08:54AM (#39960432)
I like the Quantum BogoSort as a proof of this /s