Skip to content

Instantly share code, notes, and snippets.

@PHPirates
Last active January 11, 2018 15:47
Show Gist options
  • Save PHPirates/2c728aea706d2550a7b036b636cf0989 to your computer and use it in GitHub Desktop.
Save PHPirates/2c728aea706d2550a7b036b636cf0989 to your computer and use it in GitHub Desktop.
Adapted IntegerEuclids to print LaTeX
import java.math.BigInteger
/**
* The extended euclidian algorithm for two numbers (BigIntegers included). Also prints a LaTeX tabular of all the steps.
*
* Looks for `ax + by = gcd(a, b)` where `a` and `b` are the input variables.
* [gcd] contains the gcd, [x] and [y] contain `x` and `y` as seen in the previous expression.
*
* @author Ruben Schellekens
* @author Thomas Schouten
*/
open class IntegerEuclidsToLaTeX(val a: Number, val b: Number, val extended: Boolean = true) {
var x: BigInteger? = null
private set(value) {
field = value
}
var y: BigInteger? = null
private set(value) {
field = value
}
var gcd: BigInteger? = null
private set(value) {
field = value
}
/**
* Executes the extended euclidean algorithm.
*
* @return A triple of form `(x, y, gcd(a,b))` (see class documentation of [IntegerEuclidsToLaTeX]).
*/
fun execute(): Triple<BigInteger, BigInteger, BigInteger> {
// Implementation of Algorithm 2.2 of the lecture notes.
val aBig = BigInteger("$a")
val bBig = BigInteger("$b")
// Step 1: Init
var aPrime = if(aBig >= BigInteger("0")) aBig else -aBig
var bPrime = if(bBig >= BigInteger("0")) bBig else -bBig
var x1 = BigInteger("1")
var x2 = BigInteger("0")
var y1 = BigInteger("0")
var y2 = BigInteger("1")
// Extended version uses two extra columns
if (extended) {
println("\\begin{tabular}{ccccc}")
println(" & \$Q\$ & \$R\$ & \$x\$ & \$y\$ \\\\")
println(" \$$aPrime\$ & & & \$1\$ & \$0\$ \\\\")
} else {
println("\\begin{tabular}{ccc}")
println(" & \$Q\$ & \$R\$ \\\\")
println(" \$$aPrime\$ & & \\\\")
}
// Step 2: Loop
while (bPrime > BigInteger.valueOf(0)) {
val q = BigInteger.valueOf(Math.floor(aPrime.toDouble() / bPrime.toDouble()).toLong())
val r = aPrime - q * bPrime
aPrime = bPrime
bPrime = r
val x3 = x1 - q * x2
val y3 = y1 - q * y2
if (extended) {
// Print remainder of previous step, quotient, remainder, and x and y
println(" \$$aPrime\$ & \$$q\$ & \$$r\$ & \$$x2\$ & \$$y2\$ \\\\")
} else {
// Print no x and y
println(" \$$aPrime\$ & \$$q\$ & \$$r\$ \\\\")
}
x1 = x2
y1 = y2
x2 = x3
y2 = y3
}
// Step 3: Finalise
gcd = aPrime
x = if (aBig >= BigInteger("0") ) x1 else -x1
y = if (bBig >= BigInteger("0") ) y1 else -y1
println("\\end{tabular}")
return Triple(x!!, y!!, gcd!!)
}
}
import java.math.BigInteger
fun main(args: Array<String>) {
IntegerEuclidsToLaTeX(262063, 117963).execute()
IntegerEuclidsToLaTeX(62857, 64541, extended = false).execute()
IntegerEuclidsToLaTeX(BigInteger("33177078799790592463"), BigInteger("62857")).execute()
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment