package BigNum
// Credits: Pipedream
//prefer algebraic approach because of real subtraction issues
public function log(real py, real pbase) returns real
	real y = py
	real base = pbase
	real factor = 1.0
	real logy = 0.0
	real sign = 1.0
	if y < 0.
		return 0.0

	if y < 1.
		y = 1.0 / y
		sign = -1.0

	//Chop out powers of the base
	while y >= 1.0001
		if y > base
			y = y / base
			logy = logy + factor
		else
			base = SquareRoot(base)	 //If you use just one base a lot, precompute its squareroots
			factor = factor / 2.

	return sign * logy

public class BigNum_l
	int leaf = 0
	BigNum_l next = null
	static int count = 0

	construct()
		count++

	ondestroy
		count--

	//true:  want destroy
	function clean() returns boolean
		if next == null and leaf == 0
			return true
		else if next != null and next.clean()
			destroy next
			next = null
			return leaf == 0
		else
			return false


	function divSmall (int base, int denom) returns int
		int remainder = 0
		if next != null
			remainder = next.divSmall(base,denom)

		let num = leaf + remainder * base
		let quotient = num div denom
		remainder = num - quotient * denom
		leaf = quotient
		return remainder


public class BigNum
	BigNum_l list = null
	int base

	construct(int base)
		this.base = base

	ondestroy
		BigNum_l cur = list
		BigNum_l next
		while cur != null
			next = cur.next
			destroy cur
			cur = next

	function isZero() returns boolean
		BigNum_l cur = list
		while cur != null
			if cur.leaf != 0
				return false
			cur = cur.next
		return true


	function clean()
		list.clean()


	//fails if bignum is null
	//BASE() + carry must be less than MAXINT()
	function addSmall(int pcarry)
		BigNum_l cur = list
		int sum
		int carry = pcarry

		if cur == null
			cur = new BigNum_l()
			list = cur


		while carry != 0
			sum = cur.leaf + carry
			carry = sum div base
			sum = sum - carry * base
			cur.leaf = sum

			if cur.next == null
				cur.next = new BigNum_l()

			cur = cur.next


	// x * BASE() must be less than MAXINT()
	function mulSmall(int x)
		BigNum_l cur = list
		int product
		int remainder
		int carry = 0
		while cur != null or carry != 0
			product = x * cur.leaf + carry
			carry = product div base
			remainder = product - carry * base
			cur.leaf = remainder
			if cur.next == null and carry != 0
				cur.next = new BigNum_l()

			cur = cur.next

	//Returns remainder
	function divSmall(int denom) returns int
		return list.divSmall(base,denom)

	function lastDigit() returns int
		BigNum_l cur = list
		BigNum_l next = cur.next
		while next != null
			cur = next
			next = cur.next

		return cur.leaf

	function dump() returns string
		BigNum_l cur = this.list
		string s = ""
		while cur != null
			s = I2S(cur.leaf)+" "+s
			cur = cur.next
		return s