Python and Viv · Numerics
Bisection
What to notice
- The loop, the tuple assignment
lo, flo = mid, fmidand the two resultsreturn root, stepsare the same in both. raise ValueError(...)isstop("..."). Python's caller could catch it; nothing catches a Vivstop.- A
defis a value in both:bisect(cubic, 2.0, 3.0, 1e-10)passes the function by name. x ** 3isx ^ 3.- The loop
for tol in [1e-2, 1e-4, 1e-8]walks an array literal in Viv as it walks a list in Python.
Python bisection.py · 32 lines
Viv bisection.viv · 42 lines
py2viv translated from bisection.py
What py2viv adds before the program
(nothing)
(nothing)
32 lines: a header and the guard functions its translation calls
1###
2Translated from bisection.py by py2viv 0.2.0 (numeric Python -> Viv).
3Python source sha256: 5e48a23567c43984ad10937131386966fe2925267f45c337148c2c28a32da687
4Each print(...) is one print(...) line; fmt(x) writes a float as Python's repr does.
5A `raise`, a failed assert and every guard `stop` with Python's exception line.
6###
7
8#| An int result, as Python's int: a -0.0 becomes 0 (an int has no sign on zero), and the run
9#| stops at 2^53, past which a double no longer holds every integer (Python's int does).
10def py_int(x) {
11 if abs(x) >= 9007199254740992 {
12 stop("py2viv: an integer reached 2^53; Python's int is exact there and a double is not")
13 }
14 return x + 0.0
15}
16
17#| a ** b with a float, as CPython's float_pow: ZeroDivisionError for 0.0 to a negative
18#| power, OverflowError when a finite pair overflows; a negative base to a fractional power
19#| (a complex number in Python) stops.
20def py_fpow(a, b) {
21 if a == 0 and b < 0 {
22 stop("ZeroDivisionError: 0.0 cannot be raised to a negative power")
23 }
24 if a < 0 and abs(a) < 1.0 / 0.0 and floor(b) != b and abs(b) < 1.0 / 0.0 {
25 stop("py2viv: a negative number to a fractional power is a complex number in Python")
26 }
27 r = a ^ b
28 if abs(r) == 1.0 / 0.0 and abs(a) < 1.0 / 0.0 and abs(b) < 1.0 / 0.0 {
29 stop("OverflowError: (34, 'Result too large')")
30 }
31 return r
32}
1 bisection: halve the bracket until it is small
4def bisect(f, lo, hi, tol):
5 flo = f(lo)
6 if flo * f(hi) > 0:
7 raise ValueError("the bracket does not change sign")
8 steps = 0
9 while hi - lo > tol:
10 mid = 0.5 * (lo + hi)
11 fmid = f(mid)
12 if flo * fmid <= 0:
13 hi = mid
14 else:
15 lo, flo = mid, fmid
16 steps += 1
17 return 0.5 * (lo + hi), steps
2def bisect(f, lo, hi, tol) {
3 flo = f(lo)
4 if flo * f(hi) > 0 {
5 stop("the bracket does not change sign")
6 }
7 steps = 0
8 while hi - lo > tol {
9 mid = 0.5 * (lo + hi)
10 fmid = f(mid)
11 if flo * fmid <= 0 {
12 hi = mid
13 }
14 else {
15 lo, flo = mid, fmid
16 }
17 steps += 1
18 }
19 return 0.5 * (lo + hi), steps
20}
37def bisect(f, lo, hi, tol) {
38 flo = f(lo)
39 if flo * f(hi) > 0 {
40 stop("ValueError: the bracket does not change sign")
41 }
42 steps = 0
43 while hi - lo > tol {
44 mid = 0.5 * (lo + hi)
45 fmid = f(mid)
46 if flo * fmid <= 0 {
47 hi = mid
48 }
49 else {
50 lo = mid
51 flo = fmid
52 }
53 steps = py_int(steps + 1)
54 }
55 return 0.5 * (lo + hi), steps
56}
2 a cubic with one real root
20def cubic(x):
21 return x ** 3 - 2.0 * x - 5.0
22
23root, steps = bisect(cubic, 2.0, 3.0, 1e-10)
24print(f"root {root:.10f} after {steps} halvings, f(root) = {cubic(root):.2e}")
23def cubic(x) {
24 return x ^ 3 - 2.0 * x - 5.0
25}
26
27root, steps = bisect(cubic, 2.0, 3.0, 1e-10)
28print(f"root {root:.10f} after {steps:d} halvings, f(root) = {cubic(root):.2e}")
58def cubic(x) {
59 return py_fpow(x, 3) - 2.0 * x - 5.0
60}
61root, steps = bisect(cubic, 2.0, 3.0, 1e-10)
62print("root", fmt(root, ".10f"), "after", fmt(steps + 0.0, "d"), "halvings, f(root) =", fmt(cubic(root), ".2e"))
3 the bracket shrinks by half each step
27for tol in [1e-2, 1e-4, 1e-8]:
28 r, n = bisect(cubic, 2.0, 3.0, tol)
29 print(f"tol {tol:.0e}: {n:2d} steps, root {r:.8f}")
31for tol in [1e-2, 1e-4, 1e-8] {
32 r, n = bisect(cubic, 2.0, 3.0, tol)
33 print(f"tol {tol:.0e}: {n:2d} steps, root {r:.8f}")
34}
64py_v1 = [0.01, 0.0001, 1e-08]
65for py_i2 to 3 {
66 tol = py_v1[py_i2]
67 r, n = bisect(cubic, 2.0, 3.0, tol)
68 print("tol ", fmt(tol, ".0e"), ": ", fmt(n + 0.0, "2d"), " steps, root ", fmt(r, ".8f"), sep="")
69}
4 checks
32assert abs(cubic(root)) < 1e-8
37test "root" {
38 assert_near(cubic(root), 0.0, 1e-8)
39}
71if not (abs(cubic(root)) < 1e-08) {
72 stop("AssertionError")
73}
What they print
identical — the two programs print the same text.
Dimmed lines are left out of the comparison. Each Viv test block prints one PASS line; the Python checks the same facts with assert, which prints nothing.
$ python3 bisection.py
root 2.0945514816 after 34 halvings, f(root) = 2.92e-10tol 1e-02: 7 steps, root 2.09765625tol 1e-04: 14 steps, root 2.09457397tol 1e-08: 27 steps, root 2.09455149
$ viv run bisection.viv
root 2.0945514816 after 34 halvings, f(root) = 2.92e-10tol 1e-02: 7 steps, root 2.09765625tol 1e-04: 14 steps, root 2.09457397tol 1e-08: 27 steps, root 2.09455149PASS root
$ viv run bisection.py (py2viv’s translation)
The translation prints exactly what the Python prints.
root 2.0945514816 after 34 halvings, f(root) = 2.92e-10tol 1e-02: 7 steps, root 2.09765625tol 1e-04: 14 steps, root 2.09457397tol 1e-08: 27 steps, root 2.09455149