All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Divisible by B (Posted on 2023-02-10)
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.

 See The Solution Submitted by K Sengupta Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Algorithm and Program Comment 2 of 2 |
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

 Search: Search body:
Forums (0)