CODEWITHSUNDEEP
pythonalgorithmmath
MuchaZ
MuchaZ

Reputation: 421

Fastest way to perform operations on very big numbers in different bases

I receive a list of digits of very big 2^k-based numbers (k<=30, digits amount<=10^7).

What I need to do is to get two numbers (let's call them X and Y), subtract them (A=X-Y, B=Y-X) and return binary representation of A and B.

My current code looks like this:

k = int(input())
base = pow(2, k)
numbersX = stdin.readline().split()
digitsX = len(numbersA) - 1

x = 0
i = 1
while i <= digitsX:
    factor = pow(base, digitsX - i)
    x += int(numbersX[i]) * factor
    i += 1

(similar for Y)

I just simply convert received numbers to decimals, then subtract and get binary representation. It works but is very slow. Would you suggest other solution?

Sample input:
4 (for k)
6 15
2 7
So X = 6 15 = 6*16^1 + 15*16^0 = 96 + 15 = 111 (decimal)
Y = 2 7 = 2*16^1 + 7*16^0 = 32 + 7 = 39 (decimal)
A = X – Y = 111 – 39 = 72
B = Y – X = 39 – 111 = -72
Output:
01001000 (A in SM binary)
10111000 (B in U2 binary)

Upvotes: 0

Views: 202

Answers (2)

hiro protagonist
hiro protagonist

Reputation: 46869

this is a way to convert digits in any base to an integer:

def to_int(digits, base=1024):
    place = 1
    ret = 0
    for digit in reversed(digits):
        ret += place*digit
        place *= base
    return ret

if your base is always a power of 2 (2^10 = 1024) you could also do this (is probably a lot more efficient):

def to_int2(digits, log2base=10):
    ret = 0
    for digit in digits:
        ret <<= log2base
        ret += digit
    return ret

to then represent that as binary string you can do this:

print('{:0b}'.format(to_int(digits=(981, 5, 0, 1001))))
print('{:0b}'.format(to_int2(digits=(981, 5, 0, 1001))))

the result is the same for both (i assume the left-most is the most significant 'digit'; otherwise you would have to reverse the order of the 'digits'):

1111010101000000010100000000001111101001

(reading the input and the subtraction should be straight forward.)

for the example you added this would work like this:

x = to_int2(digits=(6, 15), log2base=4)
y = to_int2(digits=(2, 7), log2base=4)

print(x, y) # 111 39
diff = x-y
print('{:08b}'.format(diff))         # 01001000
print('{:08b}'.format(-diff & 0xff)) # 10110111

if you need to get the formatting and the mask dynamically, you could try something like this:

d = 111-39
bit_length = max(int.bit_length(d), int.bit_length(-d))
fmt = '{{:0{}b}}'.format(bit_length+1)
mask = (1<<bit_length+1) - 1
print(fmt.format(d))
print(fmt.format(-d & mask))

not sure if that covers all the edge cases correctly... but i am sure you get it right from there!

Upvotes: 1

Doug Currie
Doug Currie

Reputation: 41180

You could eliminate pow

x = 0
i = 1
while i <= digitsX:
    x *= base
    x += int(numbersX[i])
    i += 1

Upvotes: 0

Related Questions