Devise an algorithm to determine whether a given positive hexadecimal integer N is divisible by (B)
16, and if NOT, to find the remainder.
N can contain up to (20220)10 digits.
Note:
o Simply dividing N by (B)16 is NOT permissible.
o (B)16 is equal to 11 in base ten.
Input a hex number as a string, convert to a list and any letters to uppercase.
Will plan to go from left to right, ie loop through the list of hex digits.
Initialize carry = 0
Since we are dividing by 11, carry can be any integer from 0 to 10.
We are interested in 16 times the carry plus the current digit, but we can make that nicer and equivalent mod 11 by being interested in 5 times the carry plus the current digit. But we can make it even nicer by making a list with 11 entries of what will be the mod 11 contribution of the carry to the next carry. That list is:
prior = [0,5,10,4,9,3,8,2,7,1,6]
And prior[carry] is the contribution to the next carry.
Also, let's make a dictionary where "key" is any hex digit and "value" is the decimal equivalent.
The next carry is the mod 11 value of (currentDigit plus prior[carry])
When there are no more digits, final carry value is the answer.
[If we were not even allowed to do the mod11 step, we could make a larger dictionary where the keys would be the concatenations of every possible carry with every possible current digit (11*16=176 entries) and the values the corresponding carry. I did not write the code for this part however]
the following I believe will work on a hexadecimal integer of however many digits the programming language and machine constraints allow.
-----------------------
prior = [0,5,10,4,9,3,8,2,7,1,6]
hexDigits = {}
for i in range(16):
hexDigits[str(base2base(i,10,16))] = i
def r(str16):
""" string16 is a string version of a base 16 number
output the remainder if you divide by hex B or dec 11 """
carry = 0
list16 = list(str16.upper())
for d in list16:
carry = (prior[carry] + hexDigits[d])%11
if carry == 0:
print(str16.upper(), 'is divisible by hex B.')
return carry
|
Posted by Larry
on 2023-02-10 12:58:16 |