diff --git a/basis/RealNumbersAsBits.ML b/basis/RealNumbersAsBits.ML index 822df9e3..34a3d7ca 100644 --- a/basis/RealNumbersAsBits.ML +++ b/basis/RealNumbersAsBits.ML @@ -1,176 +1,176 @@ (* Title: Standard Basis Library: Real number support Author: David Matthews Copyright David Matthews 2023 This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA *) (* Extract the components of Real.real (double) and Real32.real (float). The formats, particularly of Real32.real, differ between 32-bit and 64-bit systems. *) structure RealNumbersAsBits: sig (* Floats. The mantissa will fit in a short int in both 32- and 64-bits . *) val floatSignBit: Real32.real -> bool and floatExponent: Real32.real -> FixedInt.int and floatMantissa: Real32.real -> FixedInt.int and floatFromBinary: {sign: bool, exp: FixedInt.int, mantissa: FixedInt.int} -> Real32.real (* Doubles. The mantissa is too large for a fixed int in 32-bit mode. *) val doubleSignBit: real -> bool and doubleExponent: real -> FixedInt.int and doubleMantissa: real -> LargeInt.int and doubleFromBinary: {sign: bool, exp: FixedInt.int, mantissa: LargeInt.int} -> real end = struct local (* IEEE-754 format. Float: 1 sign bit, 8 exponent bits, 23 mantissa bits. *) (* In native 64-bit a float is implemented as a tagged value. The top 32 bits contain the float, the lower 32-bits are zeros except for the tag. Because word values are tagged this is equivalent to a shift of 31 bits in ML. In native 32-bit and 32-in-64 a float is implemented as a boxed value. *) open LibrarySupport val floatIsTagged = wordSize = 0w8 val floatAsWord: Real32.real->word = RunCall.unsafeCast val floatAsInt: Real32.real->FixedInt.int = RunCall.unsafeCast val wordAsFloat: word->Real32.real = RunCall.unsafeCast fun byte(r: Real32.real, b: word): Word8.word = RunCall.loadByteFromImmutable(r, if bigEndian then b else 0w3-b) and setByte(r: Real32.real, b: word, v: Word8.word) = RunCall.storeByte(r, if bigEndian then b else 0w3-b, v) in fun floatSignBit (r: Real32.real): bool = if floatIsTagged then floatAsInt r < 0 else byte(r, 0w0) >= 0w128 fun floatExponent (r: Real32.real): FixedInt.int = if floatIsTagged then FixedInt.fromInt(Word.toInt(Word.andb(Word.>>(floatAsWord r, 0w23+0w31), 0wxff))) else FixedInt.fromInt( Word8.toInt(Word8.andb(byte(r, 0w0), 0wx7f)) * 2 + - Word8.toInt(Word8.andb(byte(r, 0w1), 0wx80))) + Word8.toInt(Word8.>>(byte(r, 0w1), 0w7))) fun floatMantissa (r: Real32.real): FixedInt.int = if floatIsTagged then FixedInt.fromInt(Word.toInt(Word.andb(Word.>>(floatAsWord r, 0w31), 0wx7fffff))) else (FixedInt.fromInt(Word8.toInt(Word8.andb(byte(r, 0w1), 0wx7f))) * 256 + FixedInt.fromInt(Word8.toInt(byte(r, 0w2)))) * 256 + FixedInt.fromInt(Word8.toInt(byte(r, 0w3))) fun floatFromBinary{sign: bool, exp: FixedInt.int, mantissa: FixedInt.int}: Real32.real = if floatIsTagged then let val signBit = if sign then Word.<<(0w1, 0w31+0w31) else 0w0 val expo = Word.<<(Word.fromInt(FixedInt.toInt exp), 0w23+0w31) (* This assumes that the mantissa value is not too large. *) val mant = Word.<<(Word.fromInt(FixedInt.toInt mantissa), 0w31) in wordAsFloat(Word.orb(signBit, Word.orb(expo, mant))) end else let val r: Real32.real = RunCall.allocateByteMemory(0w1, 0wx41) val b0 = Word8.orb(if sign then 0wx80 else 0w0, Word8.fromInt(FixedInt.toInt(FixedInt.quot(exp, 2)))) val () = setByte(r, 0w0, b0) (* The low order 24 bits will always fit in a word. *) val b = Word.orb(Word.<<(Word.fromInt(FixedInt.toInt exp), 0w23), Word.fromInt(FixedInt.toInt mantissa)) fun w8fromW x = Word8.fromLarge(Word.toLarge x) val () = setByte(r, 0w1, w8fromW(Word.>>(b, 0w16))) val () = setByte(r, 0w2, w8fromW(Word.>>(b, 0w8))) val () = setByte(r, 0w3, w8fromW b) val () = RunCall.clearMutableBit r in r end end local (* IEEE-754 format. Double: 1 sign bit, 11 exponent bits, 52 mantissa bits. *) open LibrarySupport (* In native 64-bit and 32-in-64 Real.real and LargeWord.word are both boxed 64-bit quantities. *) val realAsWord64: real -> LargeWord.word = RunCall.unsafeCast and word64AsReal: LargeWord.word -> real = RunCall.unsafeCast val realIsWord64 = sysWordSize = 0w8 fun byte(r: real, b: word): Word8.word = RunCall.loadByteFromImmutable(r, if bigEndian then b else 0w7-b) and setByte(r: real, b: word, v: Word8.word) = RunCall.storeByte(r, if bigEndian then b else 0w7-b, v) (* We use this mask when LargeWord.word is 64-bits. We don't write out the constant directly because it would cause an overflow when compiled in 32-bit mode even though it's not used. *) val doubleMantissaMask = LargeWord.>>(LargeWord.fromInt ~1, 0w12) in fun doubleSignBit (r: real) : bool = byte(r, 0w0) >= 0w128 fun doubleExponent (r: real): FixedInt.int = FixedInt.fromInt( Word8.toInt(Word8.andb(byte(r, 0w0), 0wx7f)) * 16 + Word8.toInt(Word8.>>(byte(r, 0w1), 0w4))) fun doubleMantissa (r: real): LargeInt.int = if realIsWord64 then LargeWord.toLargeInt(LargeWord.andb(realAsWord64 r, doubleMantissaMask)) else (((((Word8.toLargeInt(Word8.andb(byte(r, 0w1), 0wxf)) * 256 + Word8.toLargeInt(byte(r, 0w2))) * 256 + Word8.toLargeInt(byte(r, 0w3))) * 256 + Word8.toLargeInt(byte(r, 0w4))) * 256 + Word8.toLargeInt(byte(r, 0w5))) * 256 + Word8.toLargeInt(byte(r, 0w6))) * 256 + Word8.toLargeInt(byte(r, 0w7)) fun doubleFromBinary{sign: bool, exp: FixedInt.int, mantissa: LargeInt.int}: real = if realIsWord64 then (* We can construct the value as a LargeWord.word and then cast it as a real. *) let val signBit = if sign then LargeWord.<<(0w1, 0w63) else 0w0 val expo = LargeWord.<<(LargeWord.fromInt(FixedInt.toInt exp), 0w52) (* This assumes that the mantissa value is not too large. *) val mant = LargeWord.fromLargeInt mantissa in word64AsReal(LargeWord.orb(signBit, LargeWord.orb(expo, mant))) end else let val r: real = RunCall.allocateByteMemory(0w8 div wordSize, 0wx41) val b0 = Word8.orb(if sign then 0wx80 else 0w0, Word8.fromInt(FixedInt.toInt(FixedInt.quot(exp, 16)))) val () = setByte(r, 0w0, b0) val b1 = Word8.orb( Word8.<<(Word8.fromInt(FixedInt.toInt(FixedInt.rem(exp, 16))), 0w4), Word8.andb(Word8.fromLargeInt(IntInf.~>>(mantissa, 0w48)), 0wxf)) val () = setByte(r, 0w1, b1) val () = setByte(r, 0w2, Word8.fromLargeInt(IntInf.~>>(mantissa, 0w40))) val () = setByte(r, 0w3, Word8.fromLargeInt(IntInf.~>>(mantissa, 0w32))) val () = setByte(r, 0w4, Word8.fromLargeInt(IntInf.~>>(mantissa, 0w24))) val () = setByte(r, 0w5, Word8.fromLargeInt(IntInf.~>>(mantissa, 0w16))) val () = setByte(r, 0w6, Word8.fromLargeInt(IntInf.~>>(mantissa, 0w8))) val () = setByte(r, 0w7, Word8.fromLargeInt mantissa) val () = RunCall.clearMutableBit r in r end end end; \ No newline at end of file diff --git a/basis/RealToDecimalConversion.ML b/basis/RealToDecimalConversion.ML index cf3ed606..82c402a0 100644 --- a/basis/RealToDecimalConversion.ML +++ b/basis/RealToDecimalConversion.ML @@ -1,500 +1,313 @@ (* Title: Standard Basis Library: Conversion from floating point to decimal Author: David Matthews The underlying conversion code was translated from the C version of Ryu. That code is Copyright 2018 Ulf Adams and is licensed under the terms of the Apache License version 2.0 or Boost Software License, Version 1.0 + Boost Software License - Version 1.0 - August 17th, 2003 Boost Licence Permission is hereby granted, free of charge, to any person or organization obtaining a copy of the software and accompanying documentation covered by this license (the "Software") to use, reproduce, display, distribute, execute, and transmit the Software, and to prepare derivative works of the Software, and to permit third-parties to whom the Software is furnished to do so, all subject to the following: The copyright notices in the Software and this entire statement, including the above license grant, this restriction and the following disclaimer, must be included in all copies of the Software, in whole or in part, and all derivative works of the Software, unless such copies or derivative works are solely in the form of machine-executable object code generated by a source language processor. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. The ML translation and related code is copyright David Matthews 2023 - - This library is free software; you can redistribute it and/or - modify it under the terms of the GNU Lesser General Public - Licence version 2.1 as published by the Free Software Foundation. - - This library is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Lesser General Public Licence for more details. - - You should have received a copy of the GNU Lesser General Public - License along with this library; if not, write to the Free Software - Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + and is released under the Boost Licence. The remainder of the Poly/ML + system is licensed under LGPL. +*) +(* + This uses arbitrary precision arithmetic even for Real32.real (float) + values. It would be possible to do some of the arithmetic using fixed + precision integers but that's difficult on 32-bit platforms even for + float. *) - structure RealToDecimalConversion: sig - val f2decimal: Real32.real -> {sign:bool, exponent: int, mantissa: int} + val f2decimal: Real32.real -> {sign:bool, exponent: int, LargeInt.mantissa: int} val d2decimal: real -> {sign:bool, exponent: int, mantissa: LargeInt.int} end = struct (* Common functions *) (* Returns floor(log10(2^e)) for values of e between 0 and 1650. *) fun log10Pow2 e = if e < 0 orelse e > 1650 then raise General.Domain else Int.quot(e * 78913, 0x40000) (* >> 18 *) (* Returns floor(log10(5^e)) for values of e between 0 and 2620 *) and log10Pow5 e = if e < 0 orelse e > 2620 then raise General.Domain else Int.quot(e * 732923, 0x100000) (* >> 20 *) fun pow5bits e = if e < 0 orelse e > 3528 then raise General.Domain else Int.quot(e * 1217359, 0x80000) (* >> 19 *) + 1 - (* Float conversion. This generally uses int rather than LargeInt.int. *) local - val floatBias = 127 (* This is the exponent value for 1.0 *) - val floatMantissaBits = 24 - 1 (* One bit is implicit *) - val floatImplicitBit = Word.toInt(Word.<<(0w1, Word.fromInt floatMantissaBits)) + (* Keep dividing by 5 while the remainder is zero *) + fun p5 count value = + if LargeInt.rem(value, 5) <> 0 + then count + else p5 (count+1) (LargeInt.quot(value, 5)) + in + (* Returns whether value is divisible by 5 to the power p. *) + fun multipleOfPow5(value, e5) = + p5 0 value >= e5 + end - local - (* Keep dividing by 5 while the remainder is zero *) - fun p5 count value = - if Int.rem(value, 5) <> 0 - then count - else p5 (count+1) (Int.quot(value, 5)) + fun multipleOfPowerOf2(value, p) = + IntInf.andb(value, IntInf.<<(1, Word.fromInt p) - 1) = 0 + + local + val posTableSize = 326 and invTableSize = 342 + val pow5BitCount = 125 and pow5InvBitCount = 125 + + fun createInvSplit i = + let + val pow = IntInf.pow(5, i) + val pow5len = IntInf.log2 pow + 1 (* Bit length *) + val j = pow5len - 1 + pow5InvBitCount + val pow5inv = IntInf.<<(1, Word.fromInt j) div pow + 1 + in + pow5inv + end + + and createSplit i = + let + val pow = IntInf.pow(5, i) + val pow5len = IntInf.log2 pow + 1 (* Bit length *) + val shift = pow5len-pow5BitCount + val pow5 = + if shift < 0 + then IntInf.<<(pow, Word.fromInt(~shift)) + else IntInf.~>>(pow, Word.fromInt shift) in - (* Returns whether value is divisible by 5 to the power p. *) - fun multipleOfPow5(value, e5) = - p5 0 value >= e5 + pow5 end - fun multipleOfPowerOf2(value, p) = - Word.andb(Word.fromInt value, Word.<<(0w1, Word.fromInt p) - 0w1) = 0w0 + val doublePow5InvSplit = Vector.tabulate(invTableSize, createInvSplit) + and doublePow5Split = Vector.tabulate(posTableSize, createSplit) - local - val posTableSize = 47 and invTableSize = 55 - val pow5BitCount = 61 and pow5InvBitCount = 59 + (* We don't have 64-bit arithmetic on 32-bit platforms so this uses arbitrary precision + arithmetic. It might be possible to select different versions depending on the + word length. *) + fun mulShift(m: LargeInt.int, factor, shift: int): LargeInt.int = + if shift <= 32 then raise Fail "mulShift32" + else IntInf.~>>(factor*m, Word.fromInt shift) + in + fun mulPow5InvDivPow2(m, i, j) = mulShift(m, Vector.sub(doublePow5InvSplit, i), j) + and mulPow5DivPow2(m, i, j) = mulShift(m, Vector.sub(doublePow5Split, i), j) + + val doublePow5InvBitCount = pow5InvBitCount + and doublePow5BitCount = pow5BitCount + end - fun createInvSplit i = + (* Apart from the first step the remainder is common. *) + fun computeDecimal(e2: int, m2: LargeInt.int, mmShift, acceptBounds) = + let + (* Step 2: Determine the interval of valid decimal representations *) + val mm = 4 * m2 - 1 - mmShift + val mv = 4 * m2 + val mp = 4 * m2 + 2 + + (* Step 3: Convert to a decimal power base *) + val (e10, vr, vp, vm, lastRemovedDigit, vrIsTrailingZeros, vmIsTrailingZeros) = + if e2 >= 0 + then let - val pow = IntInf.pow(5, i) - val pow5len = IntInf.log2 pow + 1 (* Bit length *) - val j = pow5len - 1 + pow5InvBitCount - val pow5inv = IntInf.<<(1, Word.fromInt j) div pow + 1 + val q = log10Pow2 e2 + val e10 = q + val k = doublePow5InvBitCount + pow5bits q - 1 + val i = ~e2 + q + k + val vr = mulPow5InvDivPow2(mv, q, i) + and vp = mulPow5InvDivPow2(mp, q, i) + and vm = mulPow5InvDivPow2(mm, q, i) in - pow5inv + if q > 21 + then (e10, vr, vp, vm, 0, false, false) (* Too large to be power of 5. *) + else if LargeInt.rem(mv, 5) = 0 + then (e10, vr, vp, vm, 0, multipleOfPow5(mv, q), false) + else if acceptBounds + then (e10, vr, vp, vm, 0, false, multipleOfPow5(mm, q)) + else (e10, vr, vp - (if multipleOfPow5(mp, q) then 1 else 0), vm, 0, false, false) end - - and createSplit i = + else let - val pow = IntInf.pow(5, i) - val pow5len = IntInf.log2 pow + 1 (* Bit length *) - val shift = pow5len-pow5BitCount - val pow5 = - if shift < 0 - then IntInf.<<(pow, Word.fromInt(~shift)) - else IntInf.~>>(pow, Word.fromInt shift) + val q = log10Pow5(~ e2) + val e10 = q + e2 + val i = ~e2 - q + val k = pow5bits i - doublePow5BitCount + val j = q - k + val vr = mulPow5DivPow2(mv, i, j) + and vp = mulPow5DivPow2(mp, i, j) + and vm = mulPow5DivPow2(mm, i, j) + val lastRemovedDigit = + if q <> 0 andalso LargeInt.quot(vp-1, 10) <= LargeInt.quot(vm, 10) + then + let + val j' = q-1-(pow5bits(i+1)-doublePow5BitCount) + val lrm = LargeInt.rem(mulPow5DivPow2(mv, i+1, j'), 10) + in + lrm + end + else 0 in - pow5 + if q <= 1 + then if acceptBounds + then (e10, vr, vp, vm, lastRemovedDigit, true, mmShift = 1) + else (e10, vr, vp-1, vm, lastRemovedDigit, true, false) + else if q < 31 + then (e10, vr, vp, vm, lastRemovedDigit, multipleOfPowerOf2(mv, q-1), false) + else (e10, vr, vp, vm, lastRemovedDigit, false, false) end - val floatPow5InvSplit = Vector.tabulate(invTableSize, createInvSplit) - and floatPow5Split = Vector.tabulate(posTableSize, createSplit) - - (* We don't have 64-bit arithmetic on 32-bit platforms so this uses arbitrary precision - arithmetic. It might be possible to select different versions depending on the - word length. - The Java version uses two tables of 31 bit values which would be an - alternative. *) - fun mulShift32(m: int, factor, shift: int): int = - if shift <= 32 then raise Fail "mulShift32" - else LargeInt.toInt(IntInf.~>>(factor*LargeInt.fromInt m, Word.fromInt shift)) - in - fun mulPow5InvDivPow2(m, q, j) = mulShift32(m, Vector.sub(floatPow5InvSplit, q), j) - and mulPow5DivPow2(m, i, j) = mulShift32(m, Vector.sub(floatPow5Split, i), j) - - val floatPow5InvBitCount = pow5InvBitCount - and floatPow5BitCount = pow5BitCount - end - - fun f2d(ieeeMantissa, ieeeExponent) = - let - (* Step 1: Normalise the value. Normalised values, with exponent non-zero, - have an implicit one in the top bit position. *) - val (e2, m2) = - if ieeeExponent = 0 - then (1-floatBias-floatMantissaBits-2, ieeeMantissa) - else (ieeeExponent-floatBias-floatMantissaBits-2, ieeeMantissa + floatImplicitBit) - - val isEven = Int.rem(m2, 2) = 0 - val acceptBounds = isEven - - (* Step 2: Determine the interval of valid decimal representations (??) *) - val mmShift = if ieeeMantissa <> 0 orelse ieeeExponent <= 1 then 1 else 0 - (* Presumably this is 4* because we've subtracted 2 from e2. *) - val mm = 4 * m2 - 1 - mmShift - val mv = 4 * m2 - val mp = 4 * m2 + 2 - - (* Step 3: Convert to a decimal power base *) - val (e10, vr, vp, vm, lastRemovedDigit, vrIsTrailingZeros, vmIsTrailingZeros) = - if e2 >= 0 - then - let - val q = log10Pow2 e2 - val e10 = q - val k = floatPow5InvBitCount + pow5bits q - 1 - val i = ~e2 + q + k - val vr = mulPow5InvDivPow2(mv, q, i) - and vp = mulPow5InvDivPow2(mp, q, i) - and vm = mulPow5InvDivPow2(mm, q, i) - in - if q > 9 - then (e10, vr, vp, vm, 0, false, false) (* Too large to be power of 5. *) - else if Int.rem(mv, 5) = 0 - then (e10, vr, vp, vm, 0, multipleOfPow5(mv, q), false) - else if acceptBounds - then (e10, vr, vp, vm, 0, false, multipleOfPow5(mm, q)) - else (e10, vr, vp - (if multipleOfPow5(mp, q) then 1 else 0), vm, 0, false, false) - end - else + (* Step 4: Find the shortest decimal representation in the interval *) + val (output, removed) = + if vmIsTrailingZeros orelse vrIsTrailingZeros + then + let + fun removeVrDigits(vr, vp, vm, removed, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) = let - val q = log10Pow5(~ e2) - val e10 = q + e2 - val i = ~e2 - q - val k = pow5bits i - floatPow5BitCount - val j = q - k - val vr = mulPow5DivPow2(mv, i, j) - and vp = mulPow5DivPow2(mp, i, j) - and vm = mulPow5DivPow2(mm, i, j) - val lastRemovedDigit = - if q <> 0 andalso Int.quot(vp-1, 10) <= Int.quot(vm, 10) - then - let - val j' = q-1-(pow5bits(i+1)-floatPow5BitCount) - val lrm = Int.rem(mulPow5DivPow2(mv, i+1, j'), 10) - in - lrm - end - else 0 + val vpDiv10 = LargeInt.quot(vp, 10) + and vmDiv10 = LargeInt.quot(vm, 10) in - if q <= 1 - then if acceptBounds - then (e10, vr, vp, vm, lastRemovedDigit, true, mmShift = 1) - else (e10, vr, vp-1, vm, lastRemovedDigit, true, false) - else if q < 31 - then (e10, vr, vp, vm, lastRemovedDigit, multipleOfPowerOf2(mv, q-1), false) - else (e10, vr, vp, vm, lastRemovedDigit, false, false) + if vpDiv10 > vmDiv10 + then removeVrDigits(LargeInt.quot(vr, 10), vpDiv10, vmDiv10, removed+1, LargeInt.rem(vr, 10), + vmIsTrailingZeros andalso LargeInt.rem(vm, 10) = 0, + vrIsTrailingZeros andalso lastRemovedDigit = 0) + else removeVmDigits(vr, vp, vm, removed, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) end - (* Step 4: Find the shortest decimal representation in the interval *) - val (output, removed) = - if vmIsTrailingZeros orelse vrIsTrailingZeros - then + and removeVmDigits(vr, vp, vm, removed, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) = let - fun removeVrDigits(vr, vp, vm, removed, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) = - let - val vpDiv10 = Int.quot(vp, 10) - and vmDiv10 = Int.quot(vm, 10) - in - if vpDiv10 > vmDiv10 - then removeVrDigits(Int.quot(vr, 10), vpDiv10, vmDiv10, removed+1, Int.rem(vr, 10), - vmIsTrailingZeros andalso Int.rem(vm, 10) = 0, - vrIsTrailingZeros andalso lastRemovedDigit = 0) - else removeVmDigits(vr, vp, vm, removed, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) - end - - and removeVmDigits(vr, vp, vm, removed, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) = - let - in - if vmIsTrailingZeros andalso Int.rem(vm, 10) = 0 - then removeVmDigits(Int.quot(vr, 10), Int.quot(vp, 10), Int.quot(vm, 10), removed+1, Int.rem(vr, 10), - vmIsTrailingZeros, vrIsTrailingZeros andalso lastRemovedDigit = 0) - else - let - val lastRemovedDigit2 = - if vrIsTrailingZeros andalso lastRemovedDigit = 5 andalso Int.rem(vr, 2) = 0 - then 4 (* Don't round up *) - else lastRemovedDigit - val vrCorrect = - (vr = vm andalso (not acceptBounds orelse not vmIsTrailingZeros)) orelse lastRemovedDigit2 >= 5 - in - (vr + (if vrCorrect then 1 else 0), removed) - end - end in - removeVrDigits(vr, vp, vm, 0, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) - end - else - let - fun removeDigits(vr, vp, vm, removed, lastRemovedDigit) = + if vmIsTrailingZeros andalso LargeInt.rem(vm, 10) = 0 + then removeVmDigits(LargeInt.quot(vr, 10), LargeInt.quot(vp, 10), LargeInt.quot(vm, 10), removed+1, LargeInt.rem(vr, 10), + vmIsTrailingZeros, vrIsTrailingZeros andalso lastRemovedDigit = 0) + else let - val vpDiv10 = Int.quot(vp, 10) - and vmDiv10 = Int.quot(vm, 10) + val lastRemovedDigit2 = + if vrIsTrailingZeros andalso lastRemovedDigit = 5 andalso LargeInt.rem(vr, 2) = 0 + then 4 (* Don't round up *) + else lastRemovedDigit + val vrCorrect = + (vr = vm andalso (not acceptBounds orelse not vmIsTrailingZeros)) orelse lastRemovedDigit2 >= 5 in - if vpDiv10 > vmDiv10 - then removeDigits(Int.quot(vr, 10), vpDiv10, vmDiv10, removed+1, Int.rem(vr, 10)) - else (vr + (if vr = vm orelse lastRemovedDigit >= 5 then 1 else 0), removed) + (vr + (if vrCorrect then 1 else 0), removed) end - in - removeDigits(vr, vp, vm, 0, lastRemovedDigit) end - - in - {mantissa=output, exponent=e10+removed} - end - - in - fun f2decimal(f: Real32.real): {sign:bool, exponent: int, mantissa: int} = - let - open RealNumbersAsBits - val ieeeSign = floatSignBit f - and ieeeExponent = floatExponent f - and ieeeMantissa = floatMantissa f - in - if ieeeExponent = 255 - then raise General.Domain (* Infinities and NaN *) - else if ieeeExponent = 0 andalso ieeeMantissa = 0 - then {sign=ieeeSign, exponent=0, mantissa=0} - else - let - val {mantissa, exponent} = f2d(FixedInt.toInt ieeeMantissa, FixedInt.toInt ieeeExponent) - in - {sign=ieeeSign, exponent=exponent, mantissa=mantissa} - end - end - end - - (* Double conversion *) - local - val doubleBias = 1023 (* This is the exponent value for 1.0 *) - val doubleMantissaBits = 53 - 1 (* One bit is implicit *) - val doubleImplicitBit = IntInf.<<(1, Word.fromInt doubleMantissaBits) - - local - (* Keep dividing by 5 while the remainder is zero *) - fun p5 count value = - if LargeInt.rem(value, 5) <> 0 - then count - else p5 (count+1) (LargeInt.quot(value, 5)) - in - (* Returns whether value is divisible by 5 to the power p. *) - fun multipleOfPow5(value, e5) = - p5 0 value >= e5 - end - - fun multipleOfPowerOf2(value, p) = - IntInf.andb(value, IntInf.<<(1, Word.fromInt p) - 1) = 0 - - local - val posTableSize = 326 and invTableSize = 342 - val pow5BitCount = 125 and pow5InvBitCount = 125 - - fun createInvSplit i = - let - val pow = IntInf.pow(5, i) - val pow5len = IntInf.log2 pow + 1 (* Bit length *) - val j = pow5len - 1 + pow5InvBitCount - val pow5inv = IntInf.<<(1, Word.fromInt j) div pow + 1 in - pow5inv + removeVrDigits(vr, vp, vm, 0, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) end - - and createSplit i = + else let - val pow = IntInf.pow(5, i) - val pow5len = IntInf.log2 pow + 1 (* Bit length *) - val shift = pow5len-pow5BitCount - val pow5 = - if shift < 0 - then IntInf.<<(pow, Word.fromInt(~shift)) - else IntInf.~>>(pow, Word.fromInt shift) + fun removeDigits(vr, vp, vm, removed, lastRemovedDigit) = + let + val vpDiv10 = LargeInt.quot(vp, 10) + and vmDiv10 = LargeInt.quot(vm, 10) + in + if vpDiv10 > vmDiv10 + then removeDigits(LargeInt.quot(vr, 10), vpDiv10, vmDiv10, removed+1, LargeInt.rem(vr, 10)) + else (vr + (if vr = vm orelse lastRemovedDigit >= 5 then 1 else 0), removed) + end in - pow5 + removeDigits(vr, vp, vm, 0, lastRemovedDigit) end - val doublePow5InvSplit = Vector.tabulate(invTableSize, createInvSplit) - and doublePow5Split = Vector.tabulate(posTableSize, createSplit) + in + {mantissa=output, exponent=e10+removed} + end - (* We don't have 64-bit arithmetic on 32-bit platforms so this uses arbitrary precision - arithmetic. It might be possible to select different versions depending on the - word length. *) - fun mulShift(m: LargeInt.int, factor, shift: int): LargeInt.int = - if shift <= 32 then raise Fail "mulShift32" - else IntInf.~>>(factor*m, Word.fromInt shift) - in - fun mulPow5InvDivPow2(m, i, j) = mulShift(m, Vector.sub(doublePow5InvSplit, i), j) - and mulPow5DivPow2(m, i, j) = mulShift(m, Vector.sub(doublePow5Split, i), j) + val doubleBias = 1023 (* This is the exponent value for 1.0 *) + val doubleMantissaBits = 53 - 1 (* One bit is implicit *) + val doubleImplicitBit = IntInf.<<(1, Word.fromInt doubleMantissaBits) - val doublePow5InvBitCount = pow5InvBitCount - and doublePow5BitCount = pow5BitCount - end + val floatBias = 127 (* This is the exponent value for 1.0 *) + val floatMantissaBits = 24 - 1 (* One bit is implicit *) + val floatImplicitBit = Word.toInt(Word.<<(0w1, Word.fromInt floatMantissaBits)) - fun d2d(ieeeMantissa: LargeInt.int, ieeeExponent: int) = + fun d2decimal(r: real): {sign:bool, exponent: int, mantissa: LargeInt.int} = + let + open RealNumbersAsBits + val ieeeSign = doubleSignBit r + and ieeeExponent = doubleExponent r + and ieeeMantissa = doubleMantissa r + in + if ieeeExponent = 2047 + then raise General.Domain (* Infinities and NaN *) + else if ieeeExponent = 0 andalso ieeeMantissa = 0 + then {sign=ieeeSign, exponent=0, mantissa=0} + else let (* Step 1: Normalise the value. Normalised values, with exponent non-zero, have an implicit one in the top bit position. *) val (e2, m2) = if ieeeExponent = 0 then (1-doubleBias-doubleMantissaBits-2, ieeeMantissa) else (ieeeExponent-doubleBias-doubleMantissaBits-2, ieeeMantissa + doubleImplicitBit) - val isEven = LargeInt.rem(m2, 2) = 0 - val acceptBounds = isEven + val acceptBounds = LargeInt.rem(m2, 2) = 0 - (* Step 2: Determine the interval of valid decimal representations *) val mmShift = if ieeeMantissa <> 0 orelse ieeeExponent <= 1 then 1 else 0 - - val mm = 4 * m2 - 1 - mmShift - val mv = 4 * m2 - val mp = 4 * m2 + 2 - - (* Step 3: Convert to a decimal power base *) - val (e10, vr, vp, vm, lastRemovedDigit, vrIsTrailingZeros, vmIsTrailingZeros) = - if e2 >= 0 - then - let - val q = log10Pow2 e2 - val e10 = q - val k = doublePow5InvBitCount + pow5bits q - 1 - val i = ~e2 + q + k - val vr = mulPow5InvDivPow2(mv, q, i) - and vp = mulPow5InvDivPow2(mp, q, i) - and vm = mulPow5InvDivPow2(mm, q, i) - in - if q > 21 - then (e10, vr, vp, vm, 0, false, false) (* Too large to be power of 5. *) - else if LargeInt.rem(mv, 5) = 0 - then (e10, vr, vp, vm, 0, multipleOfPow5(mv, q), false) - else if acceptBounds - then (e10, vr, vp, vm, 0, false, multipleOfPow5(mm, q)) - else (e10, vr, vp - (if multipleOfPow5(mp, q) then 1 else 0), vm, 0, false, false) - end - else - let - val q = log10Pow5(~ e2) - val e10 = q + e2 - val i = ~e2 - q - val k = pow5bits i - doublePow5BitCount - val j = q - k - val vr = mulPow5DivPow2(mv, i, j) - and vp = mulPow5DivPow2(mp, i, j) - and vm = mulPow5DivPow2(mm, i, j) - val lastRemovedDigit = - if q <> 0 andalso LargeInt.quot(vp-1, 10) <= LargeInt.quot(vm, 10) - then - let - val j' = q-1-(pow5bits(i+1)-doublePow5BitCount) - val lrm = LargeInt.rem(mulPow5DivPow2(mv, i+1, j'), 10) - in - lrm - end - else 0 - in - if q <= 1 - then if acceptBounds - then (e10, vr, vp, vm, lastRemovedDigit, true, mmShift = 1) - else (e10, vr, vp-1, vm, lastRemovedDigit, true, false) - else if q < 31 - then (e10, vr, vp, vm, lastRemovedDigit, multipleOfPowerOf2(mv, q-1), false) - else (e10, vr, vp, vm, lastRemovedDigit, false, false) - end - - (* Step 4: Find the shortest decimal representation in the interval *) - val (output, removed) = - if vmIsTrailingZeros orelse vrIsTrailingZeros - then - let - fun removeVrDigits(vr, vp, vm, removed, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) = - let - val vpDiv10 = LargeInt.quot(vp, 10) - and vmDiv10 = LargeInt.quot(vm, 10) - in - if vpDiv10 > vmDiv10 - then removeVrDigits(LargeInt.quot(vr, 10), vpDiv10, vmDiv10, removed+1, LargeInt.rem(vr, 10), - vmIsTrailingZeros andalso LargeInt.rem(vm, 10) = 0, - vrIsTrailingZeros andalso lastRemovedDigit = 0) - else removeVmDigits(vr, vp, vm, removed, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) - end - - and removeVmDigits(vr, vp, vm, removed, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) = - let - in - if vmIsTrailingZeros andalso LargeInt.rem(vm, 10) = 0 - then removeVmDigits(LargeInt.quot(vr, 10), LargeInt.quot(vp, 10), LargeInt.quot(vm, 10), removed+1, LargeInt.rem(vr, 10), - vmIsTrailingZeros, vrIsTrailingZeros andalso lastRemovedDigit = 0) - else - let - val lastRemovedDigit2 = - if vrIsTrailingZeros andalso lastRemovedDigit = 5 andalso LargeInt.rem(vr, 2) = 0 - then 4 (* Don't round up *) - else lastRemovedDigit - val vrCorrect = - (vr = vm andalso (not acceptBounds orelse not vmIsTrailingZeros)) orelse lastRemovedDigit2 >= 5 - in - (vr + (if vrCorrect then 1 else 0), removed) - end - end - in - removeVrDigits(vr, vp, vm, 0, lastRemovedDigit, vmIsTrailingZeros, vrIsTrailingZeros) - end - else - let - fun removeDigits(vr, vp, vm, removed, lastRemovedDigit) = - let - val vpDiv10 = LargeInt.quot(vp, 10) - and vmDiv10 = LargeInt.quot(vm, 10) - in - if vpDiv10 > vmDiv10 - then removeDigits(LargeInt.quot(vr, 10), vpDiv10, vmDiv10, removed+1, LargeInt.rem(vr, 10)) - else (vr + (if vr = vm orelse lastRemovedDigit >= 5 then 1 else 0), removed) - end - in - removeDigits(vr, vp, vm, 0, lastRemovedDigit) - end - + val {mantissa, exponent} = computeDecimal(FixedInt.toInt e2, m2, mmShift, acceptBounds) in - {mantissa=output, exponent=e10+removed} + {sign=ieeeSign, exponent=exponent, mantissa=mantissa} end + end + + and f2decimal(f: Real32.real): {sign:bool, exponent: int, mantissa: int} = + let + open RealNumbersAsBits + val ieeeSign = floatSignBit f + and ieeeExponent = floatExponent f + and ieeeMantissa = floatMantissa f in - fun d2decimal(r: real): {sign:bool, exponent: int, mantissa: LargeInt.int} = + if ieeeExponent = 255 + then raise General.Domain (* Infinities and NaN *) + else if ieeeExponent = 0 andalso ieeeMantissa = 0 + then {sign=ieeeSign, exponent=0, mantissa=0} + else let - open RealNumbersAsBits - val ieeeSign = doubleSignBit r - and ieeeExponent = doubleExponent r - and ieeeMantissa = doubleMantissa r + (* Step 1: Normalise the value. Normalised values, with exponent non-zero, + have an implicit one in the top bit position. *) + val (e2, m2) = + if ieeeExponent = 0 + then (1-floatBias-floatMantissaBits-2, ieeeMantissa) + else (ieeeExponent-floatBias-floatMantissaBits-2, ieeeMantissa + floatImplicitBit) + + val isEven = Int.rem(m2, 2) = 0 + val acceptBounds = isEven + + (* Step 2: Determine the interval of valid decimal representations (??) *) + val mmShift = if ieeeMantissa <> 0 orelse ieeeExponent <= 1 then 1 else 0 + + val {mantissa, exponent} = computeDecimal(FixedInt.toInt e2, FixedInt.toLarge m2, mmShift, acceptBounds) in - if ieeeExponent = 2047 - then raise General.Domain (* Infinities and NaN *) - else if ieeeExponent = 0 andalso ieeeMantissa = 0 - then {sign=ieeeSign, exponent=0, mantissa=0} - else - let - val {mantissa, exponent} = d2d(ieeeMantissa, FixedInt.toInt ieeeExponent) - in - {sign=ieeeSign, exponent=exponent, mantissa=mantissa} - end + {sign=ieeeSign, exponent=exponent, mantissa=mantissa} end + end end;