src/math/number.bend checks

raw source on the hub · import bend-collections-laws-math@1.0.0.0/src/math/number.bend as Number

1 import

import Base

Types

type EGcd source · line 20 · raw

Data

gcd(a, b) and signed Bezout coefficients split into magnitudes and a sign: neg == False: a * x == gcd + b * y (a*x - b*y == gcd) neg == True: b * y == gcd + a * x (b*y - a*x == gcd) Python's egcd would return one negative coefficient; the unsigned library returns both magnitudes and says which side carries the minus sign.

EG

@gcd:Nat -> @x:Nat -> @y:Nat -> @neg:Bool -> EGcd

Definitions

def bit_count_go source · line 26 · raw

@fuel:Nat -> @+n:Nat -> @+acc:Nat -> Nat

n halves every step, so n steps are enough

def bit_count source · line 35 · raw

@+n:Nat -> Nat

def eg_up source · line 43 · raw

@+q:Nat -> @r:EGcd -> EGcd

From the child (b, a mod b) to the parent (a, b): with q = a div b the coefficients become (y', x' + q*y') and the sign flips (Knuth 4.5.2, algorithm X, in magnitudes).

def egcd_go source · line 49 · raw

@fuel:Nat -> @+a:Nat -> @+b:Nat -> EGcd

b <= fuel throughout, as in natural.bend's gcd_go

def egcd source · line 58 · raw

@+a:Nat -> @+b:Nat -> EGcd

def prime_go source · line 65 · raw

@fuel:Nat -> @+n:Nat -> @+d:Nat -> @done:Bool -> @divides:Bool -> Bool

trial division: no d in [2, n) divides n iff none in [2, isqrt(n)] does. done is n < d*d, divides is d | n, both for the current d.

def is_prime source · line 76 · raw

@+n:Nat -> Bool