Fil-C on Nix

Filnix wiki

mbrock/filnix/nanofil

ieee.pl

IEEE 754 binary32 and binary64 arithmetic with integers only, rounding to nearest, ties to even.

Operands and results are unsigned bit patterns, never host floats. Finite intermediates are exact rationals, and round_ratio is the single rounding boundary, gradual underflow and overflow included. All public inputs must be concrete.

Predicates

K is s (binary32), d (binary64) or x (the x87 80-bit extended format of C's long double on x86-64: a sign, 15 exponent bits and a 64-bit significand whose integer bit is explicit, in the low 80 bits of the pattern). An x NaN operand follows the x87's rule instead of SSE's: when both operands are NaNs, a quiet one wins over a signaling one, else the one with the larger significand, else the first.

PredicateNotes
ieee_binaryK, Op, A, B, ROp is add, sub, mul or div
ieee_negK, A, Bflips the sign bit
ieee_sqrtK, A, Bthe square root, rounded to nearest; -0 stays -0, and a negative number gives the default NaN
ieee_convertFrom, To, A, Bbetween the two formats
ieee_from_intK, N, BN any integer
ieee_to_intK, B, Ntruncates; fails for nonfinite inputs, and the caller checks the destination integer's range
ieee_compareK, Cond, A, B, RR is 1 or 0; Cond is eq, ne, lt, le, gt, ge, o (ordered) or uo (unordered)
ieee_parseK, Chars, Ba decimal or C hexadecimal significand, without a C type suffix: the frontend selects K after removing the suffix
ieee_decimalK, B, Charsan exact decimal, not necessarily the shortest; fails for nonfinite inputs
useslists
usesdcgs
useserror

format(K, fraction bits, exponent bits, bias): the fraction excludes the integer bit, which x stores explicitly (integer_bit/2).

format
40s238127
41d52111023
42x631516383
integer_bitK, Bits

the bits of the explicit integer bit, if any; the exponent starts above it.

integer_bit
46s0
47d0
48x1
49exponent_shiftK, Sh ←
formatK, F, _, _
Sh is F + I
51decodeK, B, S, T ←
must_beinteger, B
formatK, F, E, Bias
S is B >> Sh + E
M is B /\ 1 << F−1
X is B >> Sh /\ 1 << E−1
Max is 1 << E−1
X =:= Max
→
M =:= 0
→
T = inf
else
T = nan
X =:= 0
→
P is 1−Bias−F
Sig is B /\ 1 << Sh−1
T = finiteSig, P
else
N is 1 << F + M
P is X−Bias−F
T = finiteN, P
59sign_bitsK, S, B ←
formatK, _, E, _
B is S << Sh + E
60infinityK, S, B ←
formatK, F, E, _
sign_bitsK, S, SB
B is SB + 1 << E−1 << Sh + I << F
63quietK, A, B ←
formatK, F, _, _
B is A \/ 1 << F−1
64invalidK, B ←
infinityK, 1, I
quietK, I, B

floor(log2(N)), for positive integers, without host logarithms.

67ilogN, L ←
ilogN, -1, L
68ilog0, L, L ←
!
69ilogN, A, L ←
N1 is N >> 1
A1 is A + 1
ilogN1, A1, L
71scaleN, D, E, A, B ←
E ≥ 0
→
A is N << E
B = D
else
A = N
B is D << −E

Rounding an exact positive quotient, including the halfway parity bit.

75round_evenN, D, Q ←
Q0 is N//D
R is N mod D
Twice is 2 × R
Twice > D
or
Twice =:= D
Q0 mod 2 =:= 1
!
Q is Q0 + 1
79round_evenN, D, Q ←
Q is N//D
81round_ratioK, S, 0, _, B ←
!
sign_bitsK, S, B
82round_ratioK, S, N, D, B ←
formatK, F, _, Bias
ilogN, LN
ilogD, LD
E0 is LN−LD
scaleN, D, −E0, A0, B0
A0 < B0
→
E is E0−1
else
E = E0
Emin is 1−Bias
Step is maxE, Emin−F
scaleN, D, −Step, A, C
round_evenA, C, Q
Q ≥ 1 << F + 1
→
Q1 is Q >> 1
E1 is E + 1
else
Q1 = Q
E1 is maxE, Emin
E1 > Bias
→
infinityK, S, B
Q1 < 1 << F
→
Exp = 0
Mant = Q1
else
Exp is E1 + Bias
Mant is Q1−1−I << F
E1 ≤ Bias
→
sign_bitsK, S, SB
B is SB + Exp << Sh + Mant
else
true
97finite_ratiofiniteN, E, A, B ←
scaleN, 1, E, A, B
98signed_ratioS, T, N, D ←
N is 1−2 × S × A
ieee_from_int+K, +N, -Bdet

B is the format-K bit pattern nearest the integer N, ties to even.

104ieee_from_intK, N, B ←
must_beinteger, N
N < 0
→
S = 1
else
S = 0
round_ratioK, S, A, 1, B

Trealla's abs/1 and unary minus wrap a computed native INT64_MIN; binary subtraction promotes it to a bignum on both hosts.

110magnitude_integerN, A ←
N < 0
→
A is 0−N
else
A = N
ieee_to_int+K, +B, -Nsemidet

N is the finite float B truncated toward zero. Fails for an infinity or NaN; the caller checks that N fits the destination integer.

116ieee_to_intK, B, N ←
decodeK, B, S, T
T = finite_, _
N is 1−2 × S × A//D
ieee_neg+K, +A, -Bdet

B is A with its sign bit flipped, NaNs included.

123ieee_negK, A, B ←
must_beinteger, A
sign_bitsK, 1, S
B is A xor S
ieee_sqrt+K, +A, -Bdet

B is the square root of the format-K float A, rounded to nearest, ties to even, as sqrtss, sqrtsd and fsqrt compute it (IEEE 754 5.4.1): a NaN is quieted, +0, -0 and +inf are themselves, and any other negative number, -inf included, gives the default NaN.

132ieee_sqrtK, A, B ←
decodeK, A, S, T
T ≡ nan
→
quietK, A, B
T = finite0, _
→
B = A
S =:= 1
→
T ≡ inf
→
B = A
else
T = finiteN0, P0
sqrt(N * 2^P) with P even is sqrt(N) * 2^(P/2). The root of
N * 4^G has at least G bits, G = F + 5, two more than rounding
needs; an inexact root lies strictly between Q and Q + 1, and
Q + 1/2 rounds as it does.
P0 mod 2 =:= 0
→
N1 = N0
P = P0
else
N1 is N0 × 2
P is P0−1
formatK, F, _, _
G is F + 5
M is N1 << 2 × G
isqrtM, Q
Q × Q =:= M
→
Num = Q
Den0 = 1
else
Num is 2 × Q + 1
Den0 = 2
H is P//2−G
scaleNum, Den0, H, Num1, Den
round_ratioK, 0, Num1, Den, B
isqrt+M, -Q

Q is floor(sqrt(M)) for M >= 0, by Newton's method from above.

154isqrt0, 0 ←
!
155isqrtM, Q ←
ilogM, L
X0 is 1 << L//2 + 1
isqrt_M, X0, Q
158isqrt_M, X, Q ←
Y is X + M//X//2
Y ≥ X
→
Q = X
else
isqrt_M, Y, Q
ieee_binary+K, +Op, +A, +B, -Rdet

R is A Op B in format K, Op add, sub, mul or div, rounded to nearest, ties to even, with SSE's NaN rules (x87's for K = x, header).

166ieee_binaryK, Op, A, B, R ←
decodeK, A, SA, TA
decodeK, B, SB, TB
TA ≡ nan
TB ≡ nan
K ≡ x
→
x87_nanA, B, R
TA ≡ nan
→
quietK, A, R
TB ≡ nan
→
quietK, B, R
else
binaryOp, K, SA, TA, SB, TB, R

The x87 picks between two NaN operands (Intel SDM vol. 1, 4.8.3.5).

174x87_nanA, B, R ←
QA is A >> 62 /\ 1
QB is B >> 62 /\ 1
MA is A /\ 1 << 64−1
MB is B /\ 1 << 64−1
QA > QB
→
W = A
QB > QA
→
W = B
MB > MA
→
W = B
else
W = A
quietx, W, R
180binarysub, K, SA, TA, SB, TB, R ←
SC is 1−SB
binaryadd, K, SA, TA, SC, TB, R
182binaryadd, K, SA, TA, SB, TB, R ←
TA ≡ inf
TB ≡ inf
SA ≠ SB
→
TA ≡ inf
→
infinityK, SA, R
TB ≡ inf
→
infinityK, SB, R
else
signed_ratioSA, TA, A, C
signed_ratioSB, TB, B, D
N is A × D + B × C
Den is C × D
N < 0
→
S = 1
N =:= 0
SA =:= 1
SB =:= 1
→
S = 1
else
S = 0
round_ratioK, S, Abs, Den, R
192binarymul, K, SA, TA, SB, TB, R ←
S is SA xor SB
TA ≡ inf
TB = finite0, _
or
TB ≡ inf
TA = finite0, _
→
TA ≡ inf
or
TB ≡ inf
→
infinityK, S, R
else
finite_ratioTA, A, C
finite_ratioTB, B, D
N is A × B
Den is C × D
round_ratioK, S, N, Den, R
199binarydiv, K, SA, TA, SB, TB, R ←
S is SA xor SB
TA ≡ inf
TB ≡ inf
or
TA = finite0, _
TB = finite0, _
→
TA ≡ inf
→
infinityK, S, R
TB ≡ inf
→
sign_bitsK, S, R
TB = finite0, _
→
infinityK, S, R
else
finite_ratioTA, A, C
finite_ratioTB, B, D
N is A × D
Den is C × B
round_ratioK, S, N, Den, R
ieee_convert+From, +To, +A, -Bdet

B is the format-From float A converted to format To, rounded to nearest; a NaN keeps as much of its payload as fits, aligned at the top, and is quieted.

214ieee_convertFrom, To, A, B ←
decodeFrom, A, S, T
T ≡ inf
→
infinityTo, S, B
T ≡ nan
→
formatFrom, FF, _, _
formatTo, FT, _, _
Payload is A /\ 1 << FF−1
Shift is FT−FF
Shift ≥ 0
→
P is Payload << Shift
else
P is Payload >> −Shift
infinityTo, S, I
U is I \/ P
quietTo, U, B
else
round_ratioTo, S, N, D, B
ieee_compare+K, +Cond, +A, +B, -Rdet

R is 1 when A Cond B holds for format-K floats, else 0. When either operand is a NaN only ne and uo hold, as C's != and SSE's unordered compare give.

229ieee_compareK, Cond, A, B, R ←
decodeK, A, SA, TA
decodeK, B, SB, TB
TA ≡ nan
or
TB ≡ nan
→
Order = unordered
TA ≡ inf
TB ≡ inf
→
compareOrder, SB, SA
TA ≡ inf
→
SA =:= 1
→
Order = (<)
else
Order = (>)
TB ≡ inf
→
SB =:= 1
→
Order = (>)
else
Order = (<)
else
signed_ratioSA, TA, N, D
signed_ratioSB, TB, M, C
X is N × C
Y is M × D
compareOrder, X, Y
conditionCond, Order
→
R = 1
else
R = 0
238conditioneq, =
239conditionne, O ←
O ≢ (=)
240conditionlt, <
241conditionle, O ←
memberchkO, <, =
242conditiongt, >
243conditionge, O ←
memberchkO, >, =
244conditiono, O ←
O ≢ unordered
245conditionuo, unordered
ieee_parse+K, +Cs, -Bsemidet

B is the format-K float nearest the decimal or C hexadecimal literal Cs, without a type suffix. Literals are parsed into a rational before rounding: no double rounding through binary64 for a binary32 literal.

252ieee_parseK, Cs, B ←
phraseliteralS, N, Radix, E, Cs
E ≥ 0
→
A is N × Radix^E
D = 1
else
A = N
D is Radix^−E
round_ratioK, S, A, D, B
258literalS, N, R, E ⟶
259sign1 ⟶
"-"
!
260sign0 ⟶
"+"
!
261sign0 ⟶
[]
262magnitudeN, 2, E ⟶
"0"
X
memberchkX, x, 'X'
!
significand16, N, Places
P
memberchkP, p, 'P'
E is EX−4 × Places
266magnitudeN, 10, E ⟶
significand10, N, Places
E is EX−Places
268decimal_exponentE ⟶
C
memberchkC, e, 'E'
!
269decimal_exponent0 ⟶
[]
270exponent_valueE ⟶
Ds ≢ []
digits_numberDs, 10, 0, N
E is 1−2 × S × N
273significandBase, N, Places ⟶
digit_listBase, Before
fractionBase, After
appendBefore, After, All
All ≢ []
lengthAfter, Places
digits_numberAll, Base, 0, N
277fractionBase, Ds ⟶
"."
!
digit_listBase, Ds
278fraction_, [] ⟶
[]
279digit_listBase, N|Ns ⟶
C
N < Base
!
digit_listBase, Ns
281digit_list_, [] ⟶
[]
282digit_valueC, N ←
char_codeC, V
V ≥ 48
V ≤ 57
→
N is V−48
V ≥ 97
V ≤ 102
→
N is V−87
V ≥ 65
V ≤ 70
→
N is V−55
287digits_number[], _, N, N
288digits_numberD|Ds, Base, A, N ←
A1 is A × Base + D
digits_numberDs, Base, A1, N
ieee_decimal+K, +B, -Cssemidet

Cs is an exact decimal for the finite float B, not necessarily the shortest; fails for an infinity or NaN. Every finite binary float has a terminating decimal expansion. Writing N*5^k e-k avoids padding and is exactly representable by strtof/strtod.

297ieee_decimalK, B, Cs ←
decodeK, B, S, finiteN, E
E ≥ 0
→
M is N << E
P = 0
else
M is N × 5^−E
P = E
number_charsM, MC
number_charsP, PC
S =:= 1
→
Prefix = -
else
Prefix = []
appendPrefix, MC, e, PC, Cs