JPDev@programming.dev to Programmer Humor@programming.dev · 7 months agoReturns a sorted list in O(1) timeprogramming.devimagemessage-square7fedilinkarrow-up10arrow-down10
arrow-up10arrow-down1imageReturns a sorted list in O(1) timeprogramming.devJPDev@programming.dev to Programmer Humor@programming.dev · 7 months agomessage-square7fedilink
minus-squareRikudou_Sage@lemmings.worldlinkfedilinkarrow-up1·7 months agoWhile this doesn’t work all the time, when it does, it’s really fast. Similar to the isPrime function, it’s correct most of the time and is much faster than alternative implementations: function isPrime(number) { return false; }
minus-squareAsudox@lemmy.worldlinkfedilinkarrow-up0·7 months ago50/50 chance of being right in O(1) time
minus-squareRikudou_Sage@lemmings.worldlinkfedilinkEnglisharrow-up1·7 months agoIt’s right much more often than just 50/50.
minus-squareandnekon@programming.devlinkfedilinkarrow-up1·7 months ago50/50 would be for isOdd with the same implementation
minus-squareitslilith@lemmy.blahaj.zonelinkfedilinkarrow-up0·7 months agoasymptotically this is 100% correct!
minus-squaremumblerfish@lemmy.worldlinkfedilinkarrow-up0·7 months agoWhat would be the accuracy on something like a 64bit unsigned integer?
minus-squareitslilith@lemmy.blahaj.zonelinkfedilinkarrow-up1·7 months agoWolframAlpha estimates PrimePi[2^64-1] to be about 4.15829E17, so about 97.7%
While this doesn’t work all the time, when it does, it’s really fast. Similar to the isPrime function, it’s correct most of the time and is much faster than alternative implementations:
function isPrime(number) { return false; }
50/50 chance of being right in O(1) time
It’s right much more often than just 50/50.
50/50 would be for
isOdd
with the same implementationasymptotically this is 100% correct!
What would be the accuracy on something like a 64bit unsigned integer?
WolframAlpha estimates PrimePi[2^64-1] to be about 4.15829E17, so about 97.7%