<div dir="ltr">I would like to point out that if you want correctness, you should use `Integer`. If you are using a bounded `Integral` it is expected that you are doing so because you value speed over correctness. They are _not_ `Z/n`, they are hardware values that have little to do with formal mathematics.</div><br><div class="gmail_quote gmail_quote_container"><div dir="ltr" class="gmail_attr">On Sun, Jul 20, 2025 at 12:23 PM Viktor Dukhovni <<a href="mailto:ietf-dane@dukhovni.org">ietf-dane@dukhovni.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Sun, Jul 20, 2025 at 07:08:54AM -0800, Daniil Iaitskov wrote:<br>
<br>
> one divMod and double cmp per digit can be replaced with left shift and<br>
> single cmp per digit which is faster<br>
<br>
But, sadly, at first blush not correct as written.  And the multiply is<br>
not needed, instead, as in the ByteString code, one can take the fast<br>
path when the old value is at most than 1/10th of the upper bound, fail<br>
when strictly larger, and take a bit more care when exactly equal.<br>
<br>
> CPU is optimized to work with word size values. Assuming word size is 64bit<br>
> then majority of fixed types (Word8 - Word64) fits a register.<br>
> <br>
>     {-# SPECIALIZE parse @Int #-}<br>
> <br>
> parse :: forall a. Num a => Parsec Word64 -> Word64 -> a<br>
> <br>
>    parse nextDigit s old =<br>
>       nextDigit >>= \case<br>
>          Nothing -> pure $ fromIntegral s<br>
>          Just d -> do<br>
>           let s' = 10 * s + d<br>
>               new = s' `shiftL` (finiteBitSize s' - finiteBitSize (undefined @a))<br>
>           if old > new then fail "overflow"<br>
>           else parse nextDigit s' new<br>
<br>
It looks like it might not always detect overflow.  Counter-example:<br>
<br>
    30 * 10 + 1 = 301<br>
<br>
which is 45 mod 256, which happens be larger than 30.  So the above<br>
would presumably accept "301" returning 45 as a Word8.  Overflow in<br>
addition of two positive numbers will produce an answer smaller than<br>
either, but this is not the case with multiplication by 10.<br>
<br>
See:<br>
<br>
    <a href="https://hackage-content.haskell.org/package/bytestring-0.12.2.0/docs/src/Data.ByteString.Lazy.ReadInt.html#_readDecimal" rel="noreferrer" target="_blank">https://hackage-content.haskell.org/package/bytestring-0.12.2.0/docs/src/Data.ByteString.Lazy.ReadInt.html#_readDecimal</a><br>
    <a href="https://hackage-content.haskell.org/package/bytestring-0.12.2.0/docs/src/Data.ByteString.Lazy.ReadInt.html#_digits" rel="noreferrer" target="_blank">https://hackage-content.haskell.org/package/bytestring-0.12.2.0/docs/src/Data.ByteString.Lazy.ReadInt.html#_digits</a><br>
<br>
-- <br>
    Viktor.  🇺🇦 Слава Україні!<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div><div><br clear="all"></div><div><br></div><span class="gmail_signature_prefix">-- </span><br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div>brandon s allbery kf8nh</div><div><a href="mailto:allbery.b@gmail.com" target="_blank">allbery.b@gmail.com</a></div></div></div></div></div>