I am a first-year college undergraduate studying Computer Science, and during my winter break I got bored and decided to try to learn a little bit of computational number theory. However, I quickly got stuck on the first part of Computational Number Theory by Abhijit Das because I can't seem to comprehend how his algorithm could possibly be valid for any integer entered by the user. Here is a chart taken from the book that illustrates his approach step-by-step:

enter image description here

His final answer for the case given is correct, and I understand how he generated the numbers he got at each step, but I feel that either his algorithm only works for a specific domain of numbers, or that I'm misunderstanding how to generalize his approach. My confusion stems from the fact that if I truncated his example down to say, "21", then $(12)_{256}$ is not the base-256 representation of the decimal number 21.

So am I wrong, or is the book wrong?

  • $\begingroup$ 12 would go to 12 if you were going forward right? $\endgroup$ – spaceisdarkgreen Jan 6 '17 at 2:18
  • $\begingroup$ @spaceisdarkgreen Yes. It would be the ones digit in base-256. $\endgroup$ – CaptainObvious Jan 6 '17 at 2:22
  • $\begingroup$ Multiply what by 10? How does 123 go to 4,206? I don't get this at all. $\endgroup$ – fleablood Jan 6 '17 at 3:39
  • $\begingroup$ @fleablood It's not 4,206, he's using that notation to represent each digit in base-256. So basically he multiplies 123 by 10 to get 1,230, then he gets the quotient and remainder of 1,230 when divided by 256. So the first element 4 is given by floor(1,230/4) and the second element 206 is given by 1,230 % 256. $\endgroup$ – CaptainObvious Jan 6 '17 at 3:44
  • $\begingroup$ Well, then if abc =256A+B the abcd =256(10A) +10B + d with any reducing and remainders if 10A > 256 or 10B > 256. What's not to understand? $\endgroup$ – fleablood Jan 6 '17 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.