/ 
Sidef-26.01
River stage one • 1 direct dependent • 1 total dependent
⭐ Starred 115 GitHub stars
/ Sidef::Types::Number::Quadratic

NAME

Sidef::Types::Number::Quadratic - Quadratic integer arithmetic

DESCRIPTION

This class implements quadratic integers of the form a + b√w, where a and b are rational numbers and w is a square-free integer (the discriminant). Quadratic integers are an extension of the rational numbers that include square roots.

The class provides arithmetic operations, modular arithmetic, and various utility methods for working with quadratic integers. Common applications include algebraic number theory, cryptography, and solving Pell equations.

For more information, see: https://en.wikipedia.org/wiki/Quadratic_integer

SYNOPSIS

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)

say x.powmod(100, 97)   #=> (83, 42, 5)
say y.powmod(100, 97)   #=> (83, 39, 2)

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

# Properties
say x.norm              # compute the norm: a² - b²w
say x.conj              # conjugate: a - b√w
say x.abs               # absolute value: sqrt(norm)

# Modular arithmetic
say x.powmod(100, 97)   # modular exponentiation

INHERITS

Inherits methods from:

* Sidef::Types::Number::Number

METHODS

new

Quadratic(a, b, w)
Quadratic.new(a, b, w)

Constructs a new quadratic integer representing a + b√w.

Parameters:

  • a - The rational part (default: 0)

  • b - The coefficient of the square root term (default: 0)

  • w - The discriminant/order (default: 1)

Returns: A new Quadratic object

Example:

var q = Quadratic(3, 4, 5)    # 3 + 4√5
var q2 = Quadratic(2, 1)      # 2 + √1 = 3

Aliases: call

a

q.a

Returns the rational part (real component) of the quadratic integer.

For a quadratic a + b√w, this returns a.

Returns: Number - the rational part

Aliases: re, real

b

q.b

Returns the coefficient of the square root term (imaginary component).

For a quadratic a + b√w, this returns b.

Returns: Number - the coefficient

Aliases: im, imag

w

q.w

Returns the discriminant (order) of the quadratic integer.

For a quadratic a + b√w, this returns w.

Returns: Number - the discriminant

Aliases: order

reals

q.reals

Returns the rational part and coefficient as a pair.

Returns: (Number, Number) - tuple of (a, b)

Example:

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

parts

q.parts

Returns all three components as an array.

Returns: Array - [a, b, w]

Example:

var parts = Quadratic(3, 4, 5).parts  # [3, 4, 5]

+

a + b

Addition of quadratic integers or addition with a regular number.

For quadratics with the same discriminant: (a + b√w) + (c + d√w) = (a+c) + (b+d)√w

Returns: Quadratic - the sum

Aliases: add

-

a - b

Subtraction of quadratic integers or subtraction with a regular number.

For quadratics with the same discriminant: (a + b√w) - (c + d√w) = (a-c) + (b-d)√w

Returns: Quadratic - the difference

Aliases: sub

*

a * b

Multiplication of quadratic integers or multiplication with a scalar.

For quadratics with the same discriminant: (a + b√w)(c + d√w) = (ac + bdw) + (ad + bc)√w

Returns: Quadratic - the product

Aliases: mul

/

a / b

Division of quadratic integers or division by a scalar.

For division by a number, divides both components. For division by another quadratic, multiplies by the multiplicative inverse.

Returns: Quadratic - the quotient

Aliases: ÷, div

**

a ** b

Exponentiation. Raises the quadratic integer to an integer power.

For non-integer exponents, converts to a regular number first.

Returns: Quadratic or Number - the result of exponentiation

Example:

var q = Quadratic(3, 4, 5)
say q**2        # (49, 24, 5)  = 49 + 24√5
say q**10       # very large result

Aliases: pow

%

a % b

Modulo operation. Computes a - b * floor(a/b).

For modulo with a number, applies to both components independently.

Returns: Quadratic - the remainder

Aliases: mod

++

a++
++a

Increment operator. Adds 1 to the rational part.

Returns: Quadratic - incremented value

Aliases: inc

--

a--
--a

Decrement operator. Subtracts 1 from the rational part.

Returns: Quadratic - decremented value

Aliases: dec

&

a & b

Bitwise AND operation on the components.

Applies bitwise AND to both the rational and coefficient parts.

Returns: Quadratic - result of bitwise AND

Aliases: and

|

a | b

Bitwise OR operation on the components.

Applies bitwise OR to both the rational and coefficient parts.

Returns: Quadratic - result of bitwise OR

Aliases: or

^

a ^ b

Bitwise XOR operation on the components.

Applies bitwise XOR to both the rational and coefficient parts.

Returns: Quadratic - result of bitwise XOR

Aliases: xor

<<

a << b

Left bit shift. Equivalent to multiplying by 2^b.

Returns: Quadratic - result after left shift

Aliases: lsft, shift_left

>>

a >> b

Right bit shift. Equivalent to dividing by 2^b.

Returns: Quadratic - result after right shift

Aliases: rsft, shift_right

==

a == b

Equality comparison.

Two quadratics are equal if all three components (a, b, w) are equal. A quadratic equals a number if b=0 and a equals that number.

Returns: Bool - true if equal, false otherwise

Aliases: eq

!=

a != b

Inequality comparison.

Returns: Bool - true if not equal, false otherwise

Aliases: ne

<=>

a <=> b

Three-way comparison operator (spaceship operator).

Compares lexicographically by a, then b, then w.

Returns: Number - -1 if less, 0 if equal, 1 if greater

Aliases: cmp

<

a < b

Less-than comparison based on lexicographic ordering.

Returns: Bool - true if less than, false otherwise

Aliases: lt

>

a > b

Greater-than comparison based on lexicographic ordering.

Returns: Bool - true if greater than, false otherwise

Aliases: gt

≤

a ≤ b

Less-than-or-equal comparison.

Returns: Bool - true if less than or equal, false otherwise

Aliases: <=, le

≥

a ≥ b

Greater-than-or-equal comparison.

Returns: Bool - true if greater than or equal, false otherwise

Aliases: >=, ge

abs

q.abs

Computes the absolute value (magnitude) of the quadratic integer.

Defined as sqrt(norm(q)) where norm is a² - b²w.

Returns: Number - the absolute value

Example:

var q = Quadratic(3, 4, 5)
say q.abs       # sqrt(3² - 4²*5) = sqrt(-71)

norm

q.norm

Computes the norm of the quadratic integer.

For a + b√w, the norm is a² - b²w. This is equal to the product of the quadratic with its conjugate.

Returns: Number - the norm

Example:

var q = Quadratic(3, 4, 5)
say q.norm      # 3² - 4²*5 = 9 - 80 = -71

conj

q.conj

Returns the conjugate of the quadratic integer.

For a + b√w, the conjugate is a - b√w.

Returns: Quadratic - the conjugate

Example:

var q = Quadratic(3, 4, 5)
say q.conj      # Quadratic(3, -4, 5)

neg

q.neg
-q

Returns the negation of the quadratic integer.

For a + b√w, returns -a - b√w.

Returns: Quadratic - the negation

inv

q.inv

Computes the multiplicative inverse.

For a + b√w, the inverse is a/(a²-b²w) - b/(a²-b²w)√w.

Returns: Quadratic - the multiplicative inverse

Example:

var q = Quadratic(3, 4, 5)
say q.inv       # 1/q
say q * q.inv   # Quadratic(1, 0, w) ≈ 1

sqr

q.sqr

Computes the square of the quadratic integer efficiently.

This is more efficient than q**2 or q*q.

Returns: Quadratic - the square

sgn

q.sgn

Returns the sign (unit) of the quadratic integer.

Computed as q / q.abs.

Returns: Quadratic - the sign/unit

powmod

q.powmod(n, m)

Modular exponentiation: computes q^n mod m efficiently.

Uses binary exponentiation for efficiency. Supports negative exponents by computing the modular inverse.

Parameters:

  • n - the exponent (integer)

  • m - the modulus (positive integer)

Returns: Quadratic - the result of q^n mod m

Example:

var q = Quadratic(3, 4, 5)
say q.powmod(100, 97)   # (83, 42, 5)

invmod

q.invmod(m)

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

Parameters:

  • m - the modulus

Returns: Quadratic - the modular inverse

Example:

var q = Quadratic(3, 4, 5)
var inv = q.invmod(97)
say (q * inv) % 97      # should be ≈ 1

is_zero

q.is_zero

Checks if the quadratic integer equals zero.

Returns true if both a and b are zero.

Returns: Bool - true if zero, false otherwise

is_one

q.is_one

Checks if the quadratic integer equals one.

Returns true if a=1 and b=0.

Returns: Bool - true if one, false otherwise

is_mone

q.is_mone

Checks if the quadratic integer equals minus one.

Returns true if a=-1 and b=0.

Returns: Bool - true if minus one, false otherwise

is_coprime

n.is_coprime(k)

Checks if two quadratic integers are coprime.

Two quadratics are coprime if gcd(norm(n), norm(k)) = 1.

Parameters:

  • k - another quadratic integer

Returns: Bool - true if coprime, false otherwise

floor

q.floor

Applies floor function to both components.

Returns: Quadratic - result with floored components

ceil

q.ceil

Applies ceiling function to both components.

Returns: Quadratic - result with ceiling applied to components

round

q.round(r)

Rounds both components to r decimal places.

Parameters:

  • r - number of decimal places (optional)

Returns: Quadratic - result with rounded components

float

q.float

Converts both components to floating-point numbers.

Returns: Quadratic - with floating-point components

to_n

q.to_n

Converts the quadratic integer to a regular number.

Computes a + b*sqrt(w) as a Number object.

Returns: Number - the numerical value

Example:

var q = Quadratic(3, 4, 5)
say q.to_n      # approximately 12.944271909...

Aliases: to_c

to_s

q.to_s

Converts to a string representation showing the constructor form.

Returns: String - "Quadratic(a, b, w)"

Example:

var q = Quadratic(3, 4, 5)
say q.to_s      # "Quadratic(3, 4, 5)"

pretty

q.pretty

Returns a human-readable algebraic representation.

Returns: String - "a + (b)*sqrt(w)"

Example:

var q = Quadratic(3, 4, 5)
say q.pretty    # "3 + (4)*sqrt(5)"

Aliases: stringify

dump

q.dump

Returns a string representation suitable for debugging or serialization.

Returns: String - "Quadratic(a, b, w)"

eval

q.eval(v)

Evaluates the quadratic by substituting a value for variables in the components.

Parameters:

  • v - value to substitute

Returns: Quadratic - result after evaluation

lift

q.lift

Lifts the quadratic integer by applying lift to all components.

Used in modular arithmetic contexts.

Returns: Quadratic - lifted version

MATHEMATICAL PROPERTIES

Norm and Conjugate

For a quadratic integer q = a + b√w:

  • Conjugate: conj(q) = a - b√w

  • Norm: norm(q) = q × conj(q) = a² - b²w

  • Absolute value: abs(q) = sqrt(norm(q))

Arithmetic

Quadratic integers form a ring under addition and multiplication when they share the same discriminant w. The operations are:

  • Addition: (a+b√w) + (c+d√w) = (a+c) + (b+d)√w

  • Multiplication: (a+b√w)(c+d√w) = (ac+bdw) + (ad+bc)√w

  • Inverse: 1/(a+b√w) = (a-b√w)/(a²-b²w)

EXAMPLES

# Golden ratio powers using Quadratic(0, 1, 5)
var phi = Quadratic(0, 1, 5)  # √5
say phi**2      # Quadratic(5, 0, 5) = 5

# Pell equation solutions
var x = Quadratic(1, 1, 2)    # 1 + √2
say x**2        # Quadratic(3, 2, 2) = 3 + 2√2

# Modular arithmetic
var a = Quadratic(3, 4, 5)
say a.powmod(1000, 100)  # efficient modular exponentiation

# Working with Gaussian integers (w=-1)
var z = Quadratic(3, 4, -1)   # 3 + 4i
say z.norm      # 25 (= 3² + 4²)

SEE ALSO

Sidef::Types::Number::Number

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

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.