Could 8-bit Bender compute IBAN checksums? #SoME4

International bank account numbers have a check sum. Here's an example for a German IBAN. This check sum is computed from the three other ingredients. But how do we do that? So first of all, we move country and check sum to the very right and replace the D with a 13 and E with a 14 and then the check sum is replaced with 0 0 because we don't know it prior to computation. Right? Then we take this long 24digit number and compute mod 97 giving us a number between 0 and 96 in our case 11. And then we'd subtract that from 98 giving us 87 the desired check sum. Okay. And we can compute that in Java. Um here's the Java code. We take our banks and quantonoma and the last two ingredients and concat concatenate them into a new string of length 24. Then we compute that or convert that into a big integer and compute mod 97. And of course we would expect this mod to take quite a bit of time. So what are the alternatives? So if we don't want to compute a new string, how can we concatenate these numbers into one number? Well, in the um integer realm, we would say, well, let's take the first number time 10 to the^ of 16 because 16 additional digits are left. Uh plus this number * 10^ the 6 because six additional digits are left and then this number. You can see these multiplications right here in the code. But unfortunately, uh the very first multiplication already overflows because um we would need 24 digits. But long barely has 19 digits. So this approach doesn't work at first glance. But here's the important insight. If we're going to do a mod 97 anyway, we can perform the mod 97 on these powers of 10 uh as well. And even the last number here. So you can see here's an additional mod 97 and here and here. So here are our additional mod 97s. then the um numbers are much smaller and then we get a sensible result for the final mod and the final result and this is about nine times faster. Not that it really matters but I think it's a nice side effect. Okay. Um so we can do it without big integer. Now the next question is can we do it without the long data type? Maybe your processor doesn't have a long data type. Maybe you want to do it in 32 bits instead of 64. then we have a huge problem because um this number is too big for int and even before the multiplication just passing the quantum number will already overflow in about 80% of the cases. Okay. So the next insight is to say well instead of taking the whole number and multiply it with appropriate powers of 10 mod 97 let's do it for all individual digits. For example, 10 uh to the^ of 23 mod 97 would be the 56 and 10 to the 22 would be um 25 and so on. And then the resulting numbers are much much smaller. They easily fit into an int. They would even fit into a 16- bit short. So could we do it without multiplication and division? Yes, we could replace these multiplications with a lookup table. So the 56 and the 25 and the 51 try to remember these three values are just um one column in a bigger lookup table. So this means uh 1 * 10 23 mod 97 is 56. Uh 9 * 10 23 mod 97 is 19. And for example um uh 9 * 10 6 mod 97 would be 49. Right? So just all relevant combinations. And then the multiplication turns into a lookup which you can see here. Okay. And then the intermediate results are even smaller. And what do we do with the mod or the division? Since the resulting numbers are so small, they are guaranteed to be below 16 * 97. We could perform somewhat of a binary search, finding out where in this space of uh 0 to 15 * 97 we are and then correcting or projecting into our mod 97 space in four steps. Okay, so we're down to 32 or even 16 bits. Can we do it in 8 bits? Um if you if you have a really old computer, yes, you can. So let's start with a 62. Then we add onto the rest the next looked up value and sooner or later maybe every second uh operation or so we're going to overflow into the negative number. So bite is constrained to plus 127. If we exceed that we simply project back into the correct space. We do that after every add and we will always then stay below 127 and then we need one final adjustment. Um so feel free to implement this on a 6502 processor for example then Futurama's Bender could computed or even um Arnold Schwzenegger and Terminator

modular arithmetic Summer of Math Exposition 4 0:00 IBAN 0:42 Java 1:07 64 bit 2:56 32 bit 4:40 8 bit https://de.wallpapers.com/bild/benderfuturama-bilder-i6hnext7aws27wfo.html