# -*- Mode: Python -*-

# playing with digit-based infinite numbers.
# [why: can I take a series of random base-256 digits from os.urandom() and turn it
#   into a series of base-17 numbers (for example) without wasting any of the randomness?]

# XXX fix/test negative numbers

import sys

class infnum:

    def __init__ (self, gen, neg=False, base=10, finite=False):
        self.neg = neg
        self.gen = gen
        self.base = base
        self.finite = finite

    def eval (self):
        n = 0
        m = 1
        for digit in self.gen:
            n += digit * m
            m *= self.base
        return n

    def render (self, out=sys.stdout):
        for digit in self.gen:
            out.write ('%d ' % (digit,))
        out.write ('\n')

    def next (self):
        return self.gen.next()

    def add (self, other):
        "add two infinite integers"
        return infnum (self.add_gen (other), neg=self.neg, base=self.base, finite=self.finite)

    def add_gen (self, other):
        n0 = self.gen
        n1 = other.gen
        carry = 0
        while 1:
            stop = 0
            dig0 = 0
            dig1 = 0
            try:
                dig0 = n0.next()
            except StopIteration:
                stop += 1
            try:
                dig1 = n1.next()
            except StopIteration:
                stop += 1
            if stop == 2:
                break
            dig = dig0 + dig1 + carry
            if dig >= self.base:
                carry, rem = divmod (dig, self.base)
                yield rem
            else:
                carry = 0
                yield dig
        if carry:
            yield carry

    def sub (self, other):
        "subtract two infinite integers"
        return infnum (self.sub_gen (other), neg=self.neg, base=self.base, finite=self.finite)

    def sub_gen (self, other):
        n0 = self.gen
        n1 = other.gen
        carry = 0
        while 1:
            stop = 0
            dig0 = 0
            dig1 = 0
            try:
                dig0 = n0.next()
            except StopIteration:
                stop += 1
            try:
                dig1 = n1.next()
            except StopIteration:
                stop += 1
            if stop == 2:
                break
            dig = (dig0 - carry) - dig1
            if dig < 0:
                carry = 1
                dig += self.base
                yield dig
            else:
                carry = 0
                yield dig
        if carry:
            import pdb; pdb.set_trace()

    def mul_one (self, n):
        "multiply by a finite number"
        return infnum (self.mul_one_gen (n), neg=self.neg, base=self.base, finite=self.finite)

    def mul_one_gen (self, n):
        carry = 0
        for dig in self.gen:
            r = (n * dig) + carry
            if r > self.base:
                carry, r = divmod (r, self.base)
                yield r
            else:
                carry = 0
                yield r
        if carry:
            yield carry

    def div (self, n):
        "divide by a finite number"
        # best to interpret the infinite series of digits as an infinite fraction
        # what meaning could it otherwise have?
        # maybe we should have another param indicating whether this number goes left
        #  or right of the radix point?
        return infnum (self.div_gen (n), neg=self.neg, base=self.base, finite=self.finite)

    def div_gen (self, n):
        x = 0
        while 1:
            # get x >= n
            flag = 0
            while x < n:
                if flag:
                    flag = 0
                    yield 0
                flag = 1
                try:
                    dig = self.next()
                except StopIteration:
                    yield x
                    return
                x = (x * self.base) + dig
            #print 'got x:', x
            # x >= n
            n0, x = divmod (x, n)
            #print 'n0, rem:', n0, x
            yield n0

    def basen (self, n):
        return infnum (self.basen_gen (n), neg=self.neg, base=self.base, finite=self.finite)

    def basen_gen (self, n):
        x = 0
        while 1:
            # get x >= n
            while x < n:
                try:
                    dig = self.next()
                except StopIteration:
                    yield x
                    return
                x = (x * self.base) + dig
            #print 'got x:', x
            # x >= n
            n0, x = divmod (x, n)
            #print 'n0, rem:', n0, x
            yield x

    def mul (self, other):
        "multiply two infinite integers"
        return infnum (self.mul_gen (other), neg=self.neg, base=self.base, finite=self.finite)

    # XXX ok, here's why this doesn't work.  you can't repeatedly
    #    multiply n0 by digits of n1, because n0 is not like a normal
    #    number.  Once you pull digits off of it, or use it in any
    #    way, you have exhausted it.  Without a way to 'clone' an
    #    infnum this algorithm simply won't work.

    def mul_gen (self, other):
        n0 = self
        n1 = other
        if self.finite and not other.finite:
            n0, n1 = n1, n0
        n2 = num (0)
        for dig in n1.gen:
            print 'digit of n1: %d' % (dig,)
            n2 = n0.mul_one (dig).add (n2)
            try:
                r = n2.gen.next()
            except StopIteration:
                print 'hey, it stopped!'
                r = 0
            print '  corresponding result digit: %d' % (r,)
            yield r
        print 'now rendering remaining sum...'
        for dig in n2.gen:
            yield dig

#  ...abcd  n0
#  ....xyz  n1
# X ------
# = z*n0
# + y*n0 * base
# + z*n0 * base * base

#       UC
#   ...abcd
#   ....xyz
#   -------
#  ...JIHGF F, C = divmod (z*d, base)
#  ...NMLK  K, U = divmod (y*d, base)
#  ...QPO
#  ...SR       
#  ...T
#  --------
#         .- F            
#        .-- G+K
#       .--- H+L+O
# ok, digit #0 == l[0][0]
#           #1 == l[1][1] + l[0][1]
#           #2 == l[2][2] + l[1][2] + l[0][2]
#
# problem: O(N) space, we need a generator for each row.
#   probably not avoidable?
# as we add each digit, we add another generator.
# HOWEVER, we should expect this.  multiplying two infinitely large integers together
#   is bound to cause a problem.  In reality we'll probably be multiplying by relatively
#   small integers, so we should probably let the user know which one should be the smaller
#   one?
#             

def g_num (n, base=10):
    while n:
        n, rem = divmod (n, base)
        yield rem

# from a python integer
def num (n, base=10):
    return infnum (g_num (n, base), base=base, finite=True)

def g_lit (l):
    for digit in l:
        yield digit

# from a literal (in list form)
def lit (l, base=10):
    return infnum (g_lit (l), base, finite=True)

def prng_gen (seed):
    import random
    r = random.Random()
    r.seed (seed)
    while 1:
        dig = int (r.getrandbits (8))
        #print 'dig', dig
        yield dig

def prng (seed=3141):
    return infnum (prng_gen (seed), base=256, finite=False)

def prng10_gen (seed):
    import random
    r = random.Random()
    r.seed (seed)
    while 1:
        dig = int (r.randrange (10))
        #print 'dig', dig
        yield dig

def prng10 (seed=3141):
    return infnum (prng10_gen (seed), base=10, finite=False)    

def ndigits_gen (n, count):
    i = 0
    while i < count:
        yield n.next()
        i += 1

def ndigits (n, count):
    "cap an integer at a certain number of digits"
    return infnum (ndigits_gen (n, count), base=n.base, finite=n.finite)

def t0():
    return num(3141).add(lit ([8,1,7,2])).render()
def t1():
    return num (314159265358979323846).render()
def t2():
    return num(5859).sub(num(3141)).render()
def t3():
    return num(1111).sub(num(999)).render()
def t4():
    return num(3141).mul_one(2).render()
def t5():
    return num(3141).mul_one(8).render()
def t6():
    return num(314159265358979323846).mul_one(9).render()
def t7():
    return num(3141).mul(num(2)).render()
def t8():
    return num(3141).mul(num(12)).render()
def t9():
    return num(3141).mul(num(3141)).render()
def ta():
    n0 = num (3141)
    n1 = num (6282)
    print n0.next()
    return n0.add (n1).render()
def tb():
    prng().mul_one(2).render()
def tc():
    ndigits (prng().mul_one(2), 100).render()
def td():
    ndigits (prng().div(17), 100).render()

def dist (n=17, count=1000000):
    hist = [0] * n
    g = prng().basen (n)
    for i in range (count):
        dig = g.next()
        hist[dig] += 1
    expected = count // n
    for i in range (n):
        print '%9d  %9d' % (hist[i], hist[i] - expected)
    return hist

if __name__ == '__main__':
    #t0()
    pass