/ 
Sidef-26.07
⭐ Starred 115 / Sidef::Types::Number::Quadratic

NAME

Sidef::Types::Number::Quadratic - Elements of a quadratic ring Z[t] / (t^2 - q*t - p)

DESCRIPTION

This class implements elements of a quadratic ring of the form a + b*t, where a and b are real numbers and t is a root of the characteristic polynomial t^2 = p + q*t (equivalently, t^2 - q*t - p = 0).

The ring is parameterised by two integers p and q, so each element carries four components: (a, b, p, q). Arithmetic in the ring reduces products of t using the relation t^2 = p + q*t, keeping everything as a degree-1 polynomial in t.

Common special cases include:

  • Lucas / Fibonacci sequences: Quadratic(0, 1, 1, 1) gives the element t where t^2 = t + 1 (the golden-ratio recurrence).

  • Eisenstein integers: Quadratic(a, b, -1, -1) which represents a + b*w where w = (-1 + i*sqrt(3))/2.

  • Quadratic integers of the form a + b*sqrt(w) are represented by Quadratic(a, b, w).

  • Gaussian-like integers: choosing p = -1, q = 0 gives t^2 = -1, i.e. t = i.

  • General second-order linear recurrences defined by U(n) = q*U(n-1) + p*U(n-2).

For more background see: https://en.wikipedia.org/wiki/Quadratic_integer and https://en.wikipedia.org/wiki/Lucas_sequence.

SYNOPSIS

# t satisfies t^2 = t + 1  (golden-ratio recurrence, p=1, q=1)
var t = Quadratic(0, 1, 1, 1)

say t**10   #=> Quadratic(34, 55, 1, 1)   (Fibonacci / Lucas numbers)
say t**20   #=> Quadratic(4181, 6765, 1, 1)

# Eisenstein integers
var w = Quadratic(0, 1, -1, -1)
var z = (3 + 4*w)
say z.to_n          #=> 1 + 3.46410161513775[...]i

var x = Quadratic(3, 4, 5)  # represents: 3 + 4*sqrt(5)
var y = Quadratic(6, 1, 2)  # represents: 6 + sqrt(2)

say x**10       #=> (29578174649, 13203129720, 5)
say y**10       #=> (253025888, 176008128, 2)

# Basic arithmetic
var sum  = (x + y)        # addition
var prod = (x * y)        # multiplication
var quot = (x / y)        # division

# p=1, q=0  =>  t^2 = 1
var u = Quadratic(3, 4, 1, 0)
say u.norm          #=> norm: -7
say u.conj          #=> conjugate: Quadratic(3, -4, 1, 0)
say (u * u.conj)    #=> Quadratic(-7, 0, 1, 0)
say u.abs       #=> absolute value: sqrt(-7)

# Modular exponentiation
var v = Quadratic(1, 1, 1, 1)
say v.powmod(100, 97)

INHERITS

Inherits methods from:

* Sidef::Types::Number::Number

METHODS

new

Quadratic(a, b, p, q)

Constructs a new element of the quadratic ring representing a + b*t, where t^2 = p + q*t.

Parameters:

  • a - The constant part (default: 0)

  • b - The coefficient of t (default: 0)

  • p - The constant term of the minimal polynomial t^2 - q*t - p = 0 (default: 1)

  • q - The linear term of the minimal polynomial (default: 0)

Returns: A new Quadratic object.

Example:

var e = Quadratic(3, 4, 1, 1)    # 3 + 4t,  t^2 = 1 + t
var z = Quadratic(0, 1, -1, 0)   # t,       t^2 = -1  (like i)

Aliases: call

with_value

self.with_value(a)
self.with_value(a, b)

Creates a new element in the same ring (same p and q), with specified values.

Returns: Quadratic (a, b, p, q).

Example:

var t = Quadratic(3, 4, 1, 1)
say t.with_value(7)        #=> Quadratic(7, 0, 1, 1)
say t.with_value(7, 5)     #=> Quadratic(7, 5, 1, 1)

eval

self.eval(x)

Evaluates the element as a polynomial by substituting x for t. All four components (a, b, p, q) are individually evaluated at x.

Parameters:

  • x - The value to substitute.

Returns: Quadratic after substitution.

Example:

var e = Quadratic(Poly([9,0,6]), Poly([3,4,5]), 3, 4)
say e.eval(5)   # substitutes x with 5 in the Poly objects

lift

self.lift

Lifts the element by applying lift to each of the four components. This is primarily useful after modular arithmetic to recover the representative in a larger ring.

Returns: Quadratic with lifted components.

Example:

var e = Quadratic(Mod(3, 97), Mod(4, 97), 1, 1)
say e.lift      # lift residues back

a

self.a

Returns the constant part a of the element a + b*t.

Example:

say Quadratic(3, 4, 5, 6).a      #=> 3

Aliases: re, real

b

self.b

Returns the coefficient b of the t part of the element a + b*t.

Example:

say Quadratic(3, 4, 5, 6).b      #=> 4

Aliases: im, imag

p

self.p

Returns the parameter p that defines the ring relation t^2 = p + q*t.

Example:

say Quadratic(3, 4, 5, 6).p      #=> 5

q

self.q

Returns the parameter q that defines the ring relation t^2 = p + q*t.

Example:

say Quadratic(3, 4, 5, 6).q      #=> 6

reals

self.reals

Returns the two coefficients a and b as a two-element list.

Returns: (Number, Number) — the pair (a, b).

Example:

var (a, b) = Quadratic(3, 4, 1, 1).reals     # a=3, b=4

parts

self.parts

Returns all four components as an Array.

Returns: Array [a, b, p, q].

Example:

say Quadratic(3, 4, 1, 1).parts      #=> [3, 4, 1, 1]

+

a + b

Addition of two Quadratic values in the same ring, or addition of a Quadratic and a scalar.

For elements sharing the same (p, q):

(a + b*t) + (c + d*t) = (a+c) + (b+d)*t

For scalar y: adds y to the constant part only.

Returns: Quadratic — the sum.

Example:

var x = Quadratic(1, 2, 1, 1)
var y = Quadratic(3, 4, 1, 1)
say (x + y)       #=> Quadratic(4, 6, 1, 1)
say (x + 10)      #=> Quadratic(11, 2, 1, 1)

Aliases: add

-

a - b

Subtraction of two Quadratic values in the same ring, or subtraction of a scalar from a Quadratic.

For elements sharing the same (p, q):

(a + b*t) - (c + d*t) = (a-c) + (b-d)*t

For scalar y: subtracts y from the constant part only.

Returns: Quadratic — the difference.

Example:

var x = Quadratic(5, 6, 1, 1)
var y = Quadratic(1, 2, 1, 1)
say (x - y)       #=> Quadratic(4, 4, 1, 1)

Aliases: sub

*

a * b

Multiplication in the ring, using the reduction rule t^2 = p + q*t.

For elements sharing the same (p, q):

(a + b*t)(c + d*t) = (ac + bd*p) + (ad + bc + bd*q)*t

For scalar y: multiplies both components by y.

Returns: Quadratic — the product.

Example:

var x = Quadratic(1, 1, 1, 1)    # 1 + t,  t^2 = 1 + t
say (x * x)       #=> Quadratic(2, 3, 1, 1)   (= (1+t)^2 = 2 + 3t)

Aliases: mul

/

a / b

Division of two Quadratic values in the same ring, or division of a Quadratic by a scalar.

For ring elements, computes x * conj(y) / norm(y).

For scalar y: divides both components by y.

Returns: Quadratic — the quotient.

Example:

var x = Quadratic(3, 4, 1, 0)
var y = Quadratic(7, 5, 1, 0)
say (x / y)       #=> Quadratic(1/24, 13/24, 1, 0)

Aliases: ÷, div

**

a ** b

Raises the element to an integer power using binary (square-and-multiply) exponentiation.

Negative integer exponents compute the multiplicative inverse first.

Returns: Quadratic (or Number for non-integer exponent).

Example:

var t = Quadratic(0, 1, 1, 1)    # t^2 = 1 + t
say t**10   #=> Quadratic(55, 89, 1, 1)
say t**20   #=> Quadratic(6765, 10946, 1, 1)

# Negative exponent
var e = Quadratic(1, 1, 1, 1)
say e**(-3)     # = inv(e^3)

Aliases: pow

%

a % b

Modulo operation.

When b is a plain Number, reduces both components a and b component-wise modulo b.

When b is a Quadratic in the same ring, computes the Euclidean remainder via divmod.

Returns: Quadratic — the remainder.

Example:

var a = Quadratic(5, 3, -1, -1)
var b = Quadratic(4, 7, -1, -1)
say (a % b)       #=> Quadratic(-2, 0, -1, -1)

var e = Quadratic(13, 27, 1, 1)
say (e % 7)       #=> Quadratic(6, 6, 1, 1)

Aliases: mod

++

++a

Increment: adds 1 to the constant part a, leaving b, p, q unchanged.

Returns: Quadratic — incremented value.

Example:

var e = Quadratic(3, 4, 1, 1)
say ++e     #=> Quadratic(4, 4, 1, 1)

Aliases: inc

--

--a

Decrement: subtracts 1 from the constant part a, leaving b, p, q unchanged.

Returns: Quadratic — decremented value.

Example:

var e = Quadratic(3, 4, 1, 1)
say --e     #=> Quadratic(2, 4, 1, 1)

Aliases: dec

neg

-x

Returns the negation of the element: (-a) + (-b)*t.

Returns: Quadratic

Example:

var e = Quadratic(3, 4, 1, 1)
say -e      #=> Quadratic(-3, -4, 1, 1)

sqr

x.sqr

Computes the square of the element efficiently (equivalent to x * x).

Returns: Quadratic — the square.

Example:

var e = Quadratic(1, 1, 1, 1)
say e.sqr   #=> Quadratic(2, 3, 1, 1)

abs

x.abs

Computes the absolute value (magnitude) defined as sqrt(norm(x)).

Returns: Number — the absolute value (may be complex if the norm is negative).

Example:

var e = Quadratic(3, 4, 1, 0)    # t^2 = 1
say e.abs   # sqrt(norm(e)) = sqrt(3^2 - 4^2) = sqrt(-7)

float

x.float

Converts both the a and b components to floating-point numbers, preserving p and q.

Returns: Quadratic with floating-point components.

Example:

var e = Quadratic(1/3, 1/7, 1, 1)
say e.float     # approximate floating-point components

floor

x.floor

Applies the floor function to both a and b independently.

Returns: Quadratic with floored components.

Example:

var e = Quadratic(3.7, 4.2, 1, 1)
say e.floor     #=> Quadratic(3, 4, 1, 1)

ceil

x.ceil

Applies the ceiling function to both a and b independently.

Returns: Quadratic with ceiling-applied components.

Example:

var e = Quadratic(3.1, 4.9, 1, 1)
say e.ceil      #=> Quadratic(4, 5, 1, 1)

round

x.round(r)

Rounds both a and b to r decimal places.

Parameters:

  • r - number of decimal places (optional).

Returns: Quadratic with rounded components.

Example:

var e = Quadratic(3.567, 4.321, 1, 1)
say e.round(2)      #=> Quadratic(3.57, 4.32, 1, 1)

divmod

self.divmod(other)

Euclidean division with rounding to the nearest element.

Computes the quotient q and remainder r such that self = q * other + r and the norm of r is minimised.

Returns: (Quadratic, Quadratic) — the pair (quotient, remainder).

Example:

var x = Quadratic(7, 5, 1, 1)
var y = Quadratic(2, 1, 1, 1)
var (q, r) = x.divmod(y)
say q   # rounded quotient
say r   # remainder: x - q*y

idiv

self.idiv(other)

Integer (Euclidean) quotient: returns only the quotient part of divmod.

Returns: Quadratic — the integer quotient.

Example:

var x = Quadratic(7, 5, 1, 1)
var y = Quadratic(2, 1, 1, 1)
say x.idiv(y)   # rounded-to-nearest quotient

<<

a << n

Left bit-shift: multiplies the element by 2^n.

Returns: Quadratic — result after left shift.

Example:

var e = Quadratic(1, 1, 1, 1)
say (e << 3)      #=> Quadratic(8, 8, 1, 1)  (= e * 8)

Aliases: lsft, shift_left

>>

a >> n

Right bit-shift: divides the element by 2^n.

Returns: Quadratic — result after right shift.

Example:

var e = Quadratic(8, 8, 1, 1)
say (e >> 3)      #=> Quadratic(1, 1, 1, 1)  (= e / 8)

Aliases: rsft, shift_right

powmod

x.powmod(n, m)

Modular exponentiation: computes x^n mod m efficiently using binary exponentiation, reducing modulo m at every step to keep components small.

Supports negative exponents by first computing the modular inverse.

Parameters:

  • n - the exponent (integer, may be negative).

  • m - the modulus (positive integer).

Returns: Quadratic — the result of x^n mod m.

Example:

var t = Quadratic(0, 1, 1, 1)    # t^2 = 1 + t
say t.powmod(100, 97)   # fast modular power

# Lucas / Fibonacci mod p
say t.powmod(1000, 101)

conj

x.conj

Returns the conjugate of the element.

For a + b*t, the conjugate uses the other root t' = q - t of the minimal polynomial.

Concretely:

conj(a + b*t) = (a + b*q) + (-b)*t

Returns: Quadratic — the conjugate.

Example:

var e = Quadratic(3, 4, 1, 1)
say e.conj        #=> Quadratic(7, -4, 1, 1)
say (e * e.conj)  #=> Quadratic(5, 0, 1, 1)

norm

x.norm

Computes the norm of the element.

For a + b*t, the norm is a^2 + a*b*q - b^2*p.

This equals the product of the element with its conjugate and is always a plain number (the b component of the result is zero).

Returns: Number — the norm.

Example:

var e = Quadratic(3, 4, 1, 1)
say e.norm      # 3^2 + 3*4*1 - 4^2*1 = 5
say (e.norm == (e * e.conj).a)    #=> true

trace

x.trace

Computes the trace of the element: 2*a + b*q.

The trace is the sum of the element and its conjugate:

trace(a + b*t) = (a + b*t) + conj(a + b*t) = 2*a + b*q

Returns: Number — the trace.

Example:

var e = Quadratic(3, 4, 1, 1)
say e.trace     # 2*3 + 4*1 = 10

inv

x.inv

Computes the multiplicative inverse of the element.

For a + b*t with norm N = a^2 + a*b*q - b^2*p:

inv(x) = conj(x) / N

Returns: Quadratic — the multiplicative inverse.

Example:

var e = Quadratic(3, 4, 1, 1)
say e.inv             # 1/e
say (e * e.inv)       #=> Quadratic(1, 0, 1, 1)

invmod

x.invmod(m)

Computes the modular multiplicative inverse modulo m: finds x' such that x * x' ≡ 1 (mod m).

Parameters:

  • m - the modulus (positive integer).

Returns: Quadratic — the modular inverse.

Example:

var e = Quadratic(3, 4, 1, 1)
var inv = e.invmod(97)
say ((e * inv) % 97)      #=> Quadratic(1, 0, 1, 1)

is_zero

x.is_zero

Returns true if the element is zero (both a = 0 and b = 0).

Returns: Bool

Example:

say Quadratic(0, 0, 1, 1).is_zero    #=> true
say Quadratic(1, 0, 1, 1).is_zero    #=> false

is_one

x.is_one

Returns true if the element equals the multiplicative identity (a = 1, b = 0).

Returns: Bool

Example:

say Quadratic(1, 0, 1, 1).is_one     #=> true
say Quadratic(0, 1, 1, 1).is_one     #=> false

is_mone

x.is_mone

Returns true if the element equals minus one (a = -1, b = 0).

Returns: Bool

Example:

say Quadratic(-1, 0, 1, 1).is_mone   #=> true

is_int

self.is_int

Returns true if the element is a plain integer, i.e. the b component is zero.

Returns: Bool

Example:

say Quadratic(5, 0, 1, 1).is_int     #=> true
say Quadratic(5, 3, 1, 1).is_int     #=> false

is_unit

x.is_unit

Returns true if the element is a unit (invertible), i.e. |norm(x)| = 1.

Returns: Bool

Example:

# In the ring with t^2 = t + 1, t itself has norm = -1, so it's a unit
var t = Quadratic(0, 1, 1, 1)
say t.is_unit       #=> true

is_associate

x.is_associate(y)

Returns true if x and y are associates, i.e. x = u * y for some unit u.

Equivalently, checks that x * inv(y) is a unit (or both are zero).

Parameters:

  • y - another Quadratic in the same ring.

Returns: Bool

Example:

var x = Quadratic(3, 4, 1, 1)
var u = Quadratic(0, 1, 1, 1)    # a unit (norm = -1)
say x.is_associate(x * u)   #=> true

is_coprime

x.is_coprime(y)

Returns true if x and y are coprime, i.e. gcd(norm(x), norm(y)) = 1.

Parameters:

  • y - another Quadratic in the same ring.

Returns: Bool

Example:

var x = Quadratic(3, 1, 1, 1)
var y = Quadratic(2, 1, 1, 1)
say x.is_coprime(y)     # true if their norms are coprime

is_prime

x.is_prime

Returns true if the norm of the element (in absolute value) is a prime integer.

This is a sufficient but not necessary condition for the element to be irreducible in the ring.

Returns: Bool

Example:

var e = Quadratic(1, 1, 1, 1)
say e.is_prime      # true if |norm(e)| is prime

gcd

self.gcd(other)

Computes the greatest common divisor of two elements using the Euclidean algorithm in the ring (via repeated divmod).

Parameters:

  • other - another Quadratic in the same ring.

Returns: Quadratic — a GCD (defined up to units).

Example:

var x = Quadratic(6, 0, 1, 1)
var y = Quadratic(4, 0, 1, 1)
say x.gcd(y)    # GCD in the ring

lcm

self.lcm(other)

Computes the least common multiple of two elements as:

self * other / gcd(self, other)

Returns zero if either argument is zero.

Parameters:

  • other - another Quadratic in the same ring.

Returns: Quadratic — the LCM.

Example:

var x = Quadratic(4, 0, 1, 1)
var y = Quadratic(6, 0, 1, 1)
say x.lcm(y)

<=>

a <=> b

Three-way (spaceship) comparison. Compares lexicographically first by a, then b, then p, then q.

Returns: Number — -1, 0, or 1.

Aliases: cmp

==

a == b

Equality test. Two Quadratic values are equal if all four components (a, b, p, q) are equal.

A Quadratic equals a plain number if b = 0 and a equals that number.

Returns: Bool

Example:

say Quadratic(3, 0, 1, 1) == 3      #=> true
say Quadratic(3, 1, 1, 1) == 3      #=> false

Aliases: eq

!=

a != b

Inequality test — negation of ==.

Returns: Bool

Aliases: ne

<

a < b

Less-than comparison based on the lexicographic ordering defined by <=>.

Returns: Bool

Aliases: lt

>

a > b

Greater-than comparison based on the lexicographic ordering defined by <=>.

Returns: Bool

Aliases: gt

≤

a ≤ b

Less-than-or-equal comparison.

Returns: Bool

Aliases: <=, le

≥

a ≥ b

Greater-than-or-equal comparison.

Returns: Bool

Aliases: >=, ge

&

a & b

Bitwise AND applied component-wise to a and b.

For two elements in the same ring, applies AND to each pair of matching components.

For a scalar, applies AND to the a component only.

Returns: Quadratic

Aliases: and

|

a | b

Bitwise OR applied component-wise to a and b.

Returns: Quadratic

Aliases: or

^

a ^ b

Bitwise XOR applied component-wise to a and b.

Returns: Quadratic

Aliases: xor

to_n

self.to_n

Converts the element to a regular Number (or Complex) by evaluating a + b*t at the principal root:

t = (q + sqrt(q^2 + 4*p)) / 2

When the discriminant q^2 + 4*p is negative, the result is complex.

Returns: Number (or Complex).

Example:

var t = Quadratic(0, 1, 1, 1)    # t^2 = t + 1
say t.to_n      # (1 + sqrt(5)) / 2  ≈ 1.6180339887...

Aliases: to_c

to_s

x.to_s

Returns the constructor-form string representation "Quadratic(a, b, p, q)".

Returns: String

Example:

var e = Quadratic(3, 4, 1, 1)
say e.to_s   #=> "Quadratic(3, 4, 1, 1)"

Aliases: dump

pretty

x.pretty

Same as to_s: returns the string "Quadratic(a, b, p, q)".

Returns: String

Aliases: stringify

MATHEMATICAL BACKGROUND

Ring Definition

A Quadratic lives in the quotient ring Z[t] / (t^2 - q*t - p).

Every element is written as a + b*t where t satisfies t^2 = p + q*t.

Products reduce through that relation:

(a + b*t)(c + d*t)  =  ac + (ad+bc)*t + bd*t^2
                    =  ac + (ad+bc)*t + bd*(p + q*t)
                    =  (ac + bd*p) + (ad + bc + bd*q)*t

Conjugate and Norm

The minimal polynomial x^2 - q*x - p = 0 has two roots, t and t' = q - t. For e = a + b*t:

  • Conjugate: conj(e) = a + b*t' = (a + b*q) - b*t

  • Norm: norm(e) = e * conj(e) = a^2 + a*b*q - b^2*p

  • Trace: trace(e) = e + conj(e) = 2*a + b*q

The norm and trace are always plain numbers (the t part cancels), which is why they play a central role in divisibility and primality tests.

Connection to Linear Recurrences

If U(n) is the second-order linear recurrence defined by

U(n) = q*U(n-1) + p*U(n-2) with U(0)=0, U(1)=1

then the element t^n has components (p*U(n-1), U(n)). This means fast exponentiation of Quadratic gives Lucas U/V sequences in O(log n) multiplications.

EXAMPLES

# Fibonacci numbers via t^2 = t + 1  (p=1, q=1)
func fib(n) {
    var t = Quadratic(0, 1, 1, 1)
    (t**n).b
}
say fib(10)     #=> 55
say fib(20)     #=> 6765

# Eisenstein integers
func Eisenstein(a, b) {
    Quadratic(a, b, -1, -1)
}

var w = Eisenstein(0, 1)
say 10.by {|n| (1 - w)**n - 1 -> norm.is_prime }

# Lucas numbers (same ring, different starting point)
func luc(n) {
    var t = Quadratic(0, 1, 1, 1)
    (t**n).trace
}
say luc(10)     #=> 123

# Pell-like sequence  t^2 = 2t + 1  (p=1, q=2)
var x = Quadratic(1, 1, 1, 2)
say x**5

# Gaussian integers:  t^2 = -1  (p=-1, q=0)
var i  = Quadratic(0, 1, -1, 0)  # t = i
var z  = Quadratic(3, 4, -1, 0)  # 3 + 4i
say z.norm      #=> 25   (= 3^2 + 4^2)
say z.conj      #=> Quadratic(3, -4, -1, 0)

# Modular arithmetic
var e = Quadratic(1, 1, 1, 1)
say e.powmod(100, 97)
say e.invmod(97)

SEE ALSO

Sidef::Types::Number::Number

https://en.wikipedia.org/wiki/Quadratic_integer

https://en.wikipedia.org/wiki/Lucas_sequence

https://en.wikipedia.org/wiki/Quadratic_field

AUTHOR

Daniel "Trizen" Șuteu

LICENSE

This library is free software; you can redistribute it and/or modify it under the same terms as Sidef itself.