Sulprobil
Search…
sbNRN
Compute nearest rational number to a given floating point number with a given maximal denominator
"If you don't know where you are going, you might wind up someplace else." [Yogy Berra]
Which rational number is a good proxy of π (3.1415926...)? Enter in cell A1 ‘=pi()', in cell B1 your maximal denominator (for example 10), and in cells C1:D1 ‘=sbNRN(A1,B1)' as array formula (with CTRL + SHIFT + ENTER). You will get in C1:D1 22 and 7. That means: 22/7 is the nearest rational number to π with a denominator not higher than 10. For 1000 in B1 you would get 355/113.
This algorithm does NOT necessarily find the nearest rational number to a given floating point number with a given maximal denominator and a maximal absolute error. The good message is, though, that it would then return a #NUM! error. In this case please try an individual maximal absolute error.
The author's (Oliver Aberth) original intention was to support exact computation with rational numbers, for example solving a set of linear equations with rational coefficients.
Note: The last row in this graphic does not tell us that we have successfully squared the circle. We have reached Excel's limit of accuracy.
Name
sbNRN - Compute nearest rational number to a given floating point number with a given maximal denominator
Synopsis
sbNRN(dFloat, lMaxDen, [dMaxErr])
Description
sbNRN computes the nearest rational number to a given floating point number dFloat with a given maximal denominator lMaxDen and an optional maximal error dMaxErr.
Options
dFloat
Floating point number for which you want to derive the nearest rational number
lMaxDen
Maximal denominator which you want to allow
dMaxErr
Optional - Maximal absolute error (difference between input float and output rational number)
which you want to allow
Further Reading
1
#If Win64 Then
2
Function sbNRN(dFloat As Double, lMaxDen As LongLong, _
3
Optional dMaxErr As Double = -1#) As Variant
4
#Else
5
Function sbNRN(dFloat As Double, lMaxDen As Long, _
6
Optional dMaxErr As Double = -1#) As Variant
7
#End If
8
'Computes nearest rational number to dFloat with a maximal denominator
9
'lMaxDen and a maximal absolute error dMaxErr and returns result as a
10
'variant Nominator / Denominator.
11
'See: Oliver Aberth, A method for exact computation with rational numbers,
12
' JCAM, vol 4, no. 4, 1978
13
'https://berndplumhoff.gitbook.io/sulprobil/excel/excel-vba-solutions/sbnrn
14
'Bernd Plumhoff V1.21 09-Oct-2020
15
​
16
Dim dB As Double
17
#If Win64 Then
18
Dim lA As LongLong, lSgn As LongLong
19
Dim lP1 As LongLong, lP2 As LongLong, lP3 As LongLong
20
Dim lQ1 As LongLong, lQ2 As LongLong, lQ3 As LongLong
21
#Else
22
Dim lA As Long, lSgn As Long
23
Dim lP1 As Long, lP2 As Long, lP3 As Long
24
Dim lQ1 As Long, lQ2 As Long, lQ3 As Long
25
#End If
26
​
27
If dMaxErr = -1# Then dMaxErr = 1# / (2# * CDbl(lMaxDen) ^ 2#)
28
lSgn = Sgn(dFloat): dB = Abs(dFloat)
29
lP1 = 0: lP2 = 1: lQ1 = 1: lQ2 = 0
30
​
31
Do While lMaxDen > lQ2
32
lA = Int(dB)
33
lP3 = lA * lP2 + lP1: lQ3 = lA * lQ2 + lQ1
34
#If Win64 Then
35
If Abs(dB - CDbl(lA)) < 1# / CLngLng("9223372036854775807") Then
36
#Else
37
If Abs(dB - CDbl(lA)) < 1# / 2147483647# Then
38
#End If
39
Exit Do
40
End If
41
dB = 1# / (dB - CDbl(lA))
42
lP1 = lP2: lP2 = lP3: lQ1 = lQ2: lQ2 = lQ3
43
Loop
44
​
45
If lQ3 > lMaxDen Then
46
lQ3 = lQ2: lP3 = lP2
47
If lQ2 > lMaxDen Then
48
lQ3 = lQ1: lP3 = lP1
49
End If
50
End If
51
​
52
'If absolute error exceeds 1/2Q^2 then Aberth's lemma p. 286 might not apply.
53
'But the user can override this and check the result himself.
54
If Abs(dFloat - lSgn * lP3 / lQ3) > dMaxErr Then
55
sbNRN = CVErr(xlErrNum)
56
Else
57
sbNRN = Array(lSgn * lP3, lQ3)
58
End If
59
​
60
End Function
Copied!
sbNRN.xlsm
18KB
Binary
Last modified 9mo ago
Copy link