Cs.appstate.edu



The Research Experience for Teachers Program Activity:Modular Arithmetic is a method of computation that calculates the remainder given a certain modulus (divisor). It is sometimes called clock arithmetic since it resembles how we use the clock to a modulus of 12 and then begin to count over with the remainder. For example, unless we are using military time we say that 14:00 is 2:00, because the clock goes in cycles of 12. Thus the remainder after one full cycle is 2. So 2 o’clock. Actually military time is also modular with a modulus of 24 hrs instead.The math would be written as 14(mod 12) ≡ 2. Spoken: “Fourteen mod twelve is congruent to 2.” The same way we would agree that 14:00 hrs military time is the same as 2:00 normal people time.Modular arithmetic can be done with any integer modulus. The modulus is the end of the cycle. Example: 26(mod 5) ≡ 1 because the 26 includes 5 cycles of 5 with a remainder of 1Example: 45(mod 9) ≡ 0 because 45 has 5 cycles of 9 with a remainder of 0Try these examples:28(mod 5) 100(mod 9) 325(mod 100)115(mod 12)Computers are very familiar with modular arithmetic and you can use a programming command to compute the remainder. Different programming languages use various commands like mod, modulo, or rem. Some languages use the % sign. We are going to be using Python which uses the % operator. Ex: 12%5 2On your computer go to trinket.io . This is a website where you can create and run your own python programs. Create an account so that any “trinkets” (programs) you create will be saved. Then in the home screen choose NEW TRINKET.Result WindowProgram WindowType the above two lines of code. Predict what will be printed in the Result Window. Then press run to confirm if you are correct.Try the following problems. You can use new variables for each such as b = 235%3 then print b or you can simply write a single line print (235%3).120(mod 11)2535(mod 24)1255388(mod 32)463(mod 12) + 258(mod 8)Okay so the computer makes it kind of easy, especially as the numbers get larger and you don’t have to do your own long division. But what’s the point? We can find a bunch of remainders so now how do we use them? Well one of the first things we think of in computer science is binary. Base 2. A bunch ones and zeros that your computer uses: 101000011100100101000010Base 2 is a number system that only counts up to two and when it gets to 2 it actually starts over with 0.011011100101110Then it moves over to the next place value. In fact you could think of it in terms of modular “clock” arithmetic. 0 = 0 then 1 = 1 then we’ve gone around the clock so 1 rotation(mod 2) remainder 0 is 10 = 2Since we can only have 1’s and 0’s, each place value represents 2n cycle around the clock:___1_____0_____1__ Remember each cycle goes to 2 then starts over. That means 2 cycles 1 cycle 0 cyclesa one in the first blank is 2 rotations around a clock size 2.So the binary number 101 is 1 (22 cycles) + 0(21cycle) + 1(20 cycles) = 4 + 0 + 1 = 5 in decimal form.To go from decimal to binary let’s use the modular function 5(mod 2) ≡ 1, well that gives us the last digit, but what about the number of cycles? Let’s look at it using long division:5 / 2 = 2 remainder 1 but in binary we can’t have a “2” so let’s keep going.2 / 2 = 1 remainder 01 / 2 = 0 remainder 1Look the quotients don’t do much good, but the remainders match our Binary Number, cool!100111 in binary is equivalent to 39 in decimal. Try dividing 39 by 2 like we did above. What do you notice about the remainders and the binary number for 39?39/2 . . . You probably noticed that the remainder matched the binary number, but only if you read it from the bottom up. This is one way to convert decimal numbers to binary. You can also use this method to convert decimal numbers to any other base, like base 8 (called Octal). It is time consuming to do by hand because you have to keep dividing over and over by the modulus (base) number. This is one way the modulo function comes in handy: Go back to your Trinket window. Click this link: . This is a simple base conversion program. The function takes in two values, a decimal number and a base. It uses something called recursion to keep repeating the division replacing the dividend with the integer quotient until the dividend reduces to zero and then it ends the program at the base case, number = 0.Run the program and see what it does. Here are some things to try:Change the function call print base_conversion(12,2) by changing the decimal number.Decimal NumberBinary NumberChange the function call print base_conversion(12,2) by changing the base.Decimal NumberBaseConverted NumberAdd the following two lines of code at line 14 & 15. Rerun the program and explain what it shows:print dividend,print (number%base)Delete the code from part c above and change line 10 to: return resultWhat change does this make?The variable “result” is the name of the list that keeps track of the remainders. Add a command at line 8: print result. Rerun the program. Why does the list appear in a different order at that point in the program?Finally look at the code: str1 = ''.join(str(e) for e in result). This line converts the reversed list into a string named “str1” by iterating (looping) through the list one element “e” at a time and joining each element to the string. This is what gives us the converted base number in readable form without the commas of a list.Now refresh the Trinket window by clicking on the link in step 10 going back to the original.Now that you know how the modulo works to convert between decimal and other bases, you are going to try and make your own base converter in Scratch. You should keep the Python Trinket window open for reference. The programming logic is the same. You are just using a different type of code. First in Scratch you will need to create a list to keep the remainders and several variables to keep track of the number, dividend, remainder etc. Go to the “data” section of commands and create new variables. You may use the same names as in the image below or rename them as you want.4762502540I used basically the same names as in the Trinket program. Under data also create a list and name it remainders.Drag a delete from the list commands and a set from the variable commands and place them at the beginning of your program. At the beginning of the program we want to delete the list from any previous execution. We also want to set our variable to equal an empty set. Next we want the user to be able to enter a decimal and base into the conversion program. In Scratch we can do this with an ask command that is under the sensing category. It asks the user a question and then waits for an answer. The blue answer button stores the user’s input temporarily until another question is asked. So, it is important to store a user’s input with another appropriate variable before a second question is asked. Drag a blue, ask command to your script asking the user for a number. Set the appropriate variable (under data) to store their answerDrag a second blue, ask command to your script asking the user for a base.Set the appropriate variable to store their answer.5695950187960Now we have the user’s input and each answer should be assigned to the variables decimal and base. If you click the boxes under data you can see the input stored in the data bubbles:Try running through the “asks” and seeing the answers stored correctly.The user input “asks” commands are equivalent to the python input: base_conversion(200,2). These inputs are assigned to the function inputs number and base defined in the function: def base_conversion(number,base):53721001069340You can create a function in Scratch too. It might be something you haven’t tried before, but it’s fairly simple and similar to a function in any other coding language. To create a function you go to the purple more blocks and then click Make a Block. Here you are making a block that defines the function as a set of steps you add to this block. Like in the Python example you want your function to have two inputs: decimal and base. You can add these inputs under options. Type “Convert:” then add a number input, a text input, and another number input. It should look like: Then click the ok button and a function header should appear in your script.Any commands you put under this header will take place when this block is used in a script. We are going to model our Scratch program after the Python example. Look back at the trinket and start to think about what Scratch blocks would do the same things. You should use an if/else conditional statement. The If statement should define what to do when the dividend is down to zero. (This is the base case that stops the function from repeating again. The else statement should first model the python step of renaming the dividend as the quotient rounded down to the nearest integer. Under the green operator blocks you will find a block called “floor” this rounds down.Next it should assign the remainder variable to the decimal mod base value. It should then add this remainder value to the list of remainders.4295775213360Finally, under the else statement you should recall the function using the function block with the new dividend as the decimal input and the same base input: This will rerun the function treating the quotient as the new decimal dividend. This repeats until the dividend = 0, the base case, and then it will follow the instructions under the If command.Now let’s go back to the If part of the conditional. At this point the function has run through repeating the division with smaller and smaller dividends, storing the remainder each time in the remainders list. Now that the list is complete, we want to extract that list backwards and display it as a string. One way to do this is to iterate over our list, joining each element to our empty result variable one at a time. This can be done in several different ways. Be creative. Imagine what the list looks like and how you can get each element one at a time and join them together.For example: Remainders = [ 1,0,1,1,1,1]:Result = 1Result = 1111Result = 11Result = 11110Result = 111Result = 111101We want it to join the elements one by one getting it to reverse the list as it goes.42481501028701885950102870Some helpful blocks: There are many others you can use. You may want to create another list or other variables. Start with what you think might work and try it out.3086100262255 In order to complete your program you will need to call the function under your original code block and then display result: For example: Test your program with several different values. Remember you can watch what is happening by clicking the box by your list to display it while your program is running. Spend time debugging your program so it works with any input. Turn in your work according to your teacher’s instructions. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download