For the people who have worked with assembly programming they will be really use to these. In the past CPUs did not have multiply and you often had a table of the fastest way to multiply a numbers. Which you guessed it was shifts (which is like a square) and addition

@NoNameAtAll2

2 жыл бұрын

even modern cpus have shortcuts for squaring and for multiplying by small numbers, so this algo is still benefitial

@klaxoncow

2 жыл бұрын

Johnny Ball covered this on Numberphile before - search "Russian multiplication". Let's call the two numbers A and B. With number A, we shift all the bits to the right once. The rightmost bit "falls out" of the number and typically gets shifted into a flag on most CPUs - let's say our CPU shifts the bit out of the right into the carry flag. So, the carry flag now contains the rightmost (least significant) bit of number A. If it's a one, then we add number B to our running total. If it's a zero, carry on (so you could code that as a "branch if carry not set" over a "add B to total" instruction). Then we shift B left one, which doubles it. Then we do it again. Shift A to the right. The rightmost bit falls out into the carry flag. If it's a one, then we add B (which we've just doubled, remember) to the running total. Shift B left one, doubling it again. Shift A to the right. If it's a one, then add B (now four times bigger than it originally was, as we're shifting it left every round) to the running total. You keep doing this until you've shifted every original bit of A out of the right side. Stop. You've multiplied the two numbers together and your answer is in the running total register. And all we did was shifting bits left and right, and simple addition. And there's only as many "rounds" of this as there are bits in A. Another bit of useful binary maths is that the result cannot be more than twice the number of bits in B. That is, if A and B are 8-bit numbers, the result register only needs to be 16-bits - as it's just not possible for two 8-bit numbers to multiply to more than a 16-bit number. Indeed, if you're implementing this algorithm, then stick B in a register with twice as many bits and have your "running total" register be twice as many bits. Then you can run the algorithm blindly. Which is, as you may have guessed, what the CPU's actually doing in the circuitry with a hardware multiply. It's just multiplying by 2 - which, in binary, is nothing more than shifting all the bits to the left once - and addition. So, yeah, it's basically the same algorithm as this video, but working in a higher order. So multiplication -> exponential. And multiplying by 2 -> squaring. And addition -> multiplication.

@RegrinderAlert

2 жыл бұрын

@@NoNameAtAll2 Are those tables actually part of the CPU (making use of microcode) or done by a compiler?

@NoNameAtAll2

2 жыл бұрын

@@RegrinderAlert multipliers are simple enough to be just logic gates what I was talking about is "check if top 48 bits are 0, so we don't need to wait/use most of the circuit" that is too, simple enough to be just logic about compilers... idk how common the explicit "square" command is in processors

@FrankHarwald

2 жыл бұрын

yes, except that's a shift & add algorithm, & shifts aren't like squaring but like multiplying by a power of 2.

I think the last bit of the video is facinating - that you could perform an attack to work out a key based on the CPU time to calculate a square vs a square & multipy. A great example of the theoretical mathematics being ideal vs. the real world implementation being fundamentally vulnerable.

@nebuleon

2 жыл бұрын

Yes! And the technical term for it is a "timing attack". Timing attacks can be so insidious that you need to resort to assembly language just to get everything out of the way. Dr Pound's example has us doing an "always multiply", multiplying by one (the multiplication identity) after squaring for an unset bit in the exponent, so that we execute the algorithm in constant time. However, using a statement like [if (bit is zero) { multiplicand = one; } else { multiplicand = base; }] to do this "always multiplication" can end up in the *branch predictor's way.* If there are lots of zeroes in your key, it's going to take the "if" path more of the time; conversely, if there are lots of ones in your key, it's going to take the "else" path more of the time. Either way, the branch predictor will execute it faster than if the key were evenly-distributed ones and zeroes. To execute *that* in constant time, the CPU has to have a branchless test instruction to set the new multiplicand. Either you validate that the compiler uses the branchless instruction in your C code (say), or you write at least that part of the algorithm in assembly language. Edit: Or use the Montgomery form of the numbers, per David Gillies's comment, which makes it easier to have constant-time algorithms

@2Cerealbox

2 жыл бұрын

In data centers that have servers that the government uses, the government requires that their servers are plugged into an air-gapped power supply, unconnected to the power that every other server uses, so that a spy couldn't surreptitiously measure changes in their power usage. These are surprisingly effective attacks.

@mbican

2 жыл бұрын

That's why cryptographic implementation need to have constant time, no optimization allowed for multiplication by zero.

@domogdeilig

2 жыл бұрын

@@nebuleon Multiply by base^binary. Thus if there is a 0, it will be multiplied by 1, and for 1 it's the ordinary multiply. As both x^n where n is 0 or 1 is easily calculated that should be same time (?).

@justinreusnow

2 жыл бұрын

Why not just simply add a random sleep at the end of the algorithm? The size of the sleep would be a question, but if it’s a random amount each time that is sufficiently large to mask any work being done (or lack there of), it would remove this timing attack issue. It’s certainly wasteful to simply sleep, but it’s also wasteful to do unnecessary calculations to remain in constant time, no?

Note that for RSA and similar, the modular multiplication operation itself can be quite expensive, so modern implementations typically convert the numbers involved to an intermediate representation, called a Montgomery form, after Peter Montgomery. The binary exponentiation method can use Montgomery forms throughout, so only at the end is the result converted back to a conventional representation. Montgomery multiplication is also resistant to the side channel attacks mentioned at the end of the video.

@andrewharrison8436

2 жыл бұрын

Now I have to look up Montgomery forms - or wait for the Computerphile video. I do like internet rabbit holes.

@locusf2

2 жыл бұрын

@@andrewharrison8436 also look up Montgomery Ladder which is the similar algorithm for elliptic curves

@Czeckie

Жыл бұрын

fascinating, I had no idea this exists

Dr Pounds breadth and depth of knowledge in computer science never cease to amaze me!! "Man from the future"

@Ins4n1ty_

2 жыл бұрын

Absolutely, but this specific piece of knowledge is pretty much common knowledge for anyone in CS. I studied this in college about 7 years ago, it was NOT a fun time since we had a pretty bad professor...

@quincy2142

2 жыл бұрын

Not necessarily the breadth, but connecting the theoretical with the practical. Bit on timing attacks was pretty nice.

@thuokagiri5550

2 жыл бұрын

@@quincy2142 he has a very impeccable pedagogy

@jaydeep-p

Жыл бұрын

Even if he doesn't have the knowledge I still like his teaching style, it's engaging and fun.

This is also known as "Fast Binary Exponentiation", which calculates pow(a, b, mod) in logarithmic time.

Interesting algorithm. At first I thought it were just going to be a simple, "first we build our list of binary equivalents and then just multiply them all together in the end." As an example, calculate 3^1, 3^2, 3^4, 3^8, 3^16, etc. And then choose the values our exponent actually contains. Then the slight of hands of mathematicians came in at 9:40 and made things far far simpler and much easier to execute in practice.

@pikasnoop6552

2 жыл бұрын

You might have noticed that Mike said that this was the left to right method. Yours (with taking the modulus) is the right to left variant and is just as quick.

Also called russian peasant multiplication. It works for any power operation tbh, not only scalar multiplication. The power operator on matrix can for instance be used to compute large fibonacci numbers very quickly using the matrix 2x2 [1, 1, 1, 0]

9:34 It's actually not the minimum number of operations. For example, to make 31 by this method takes 8 operations (SMSMSMSM), whereas the minimum is only 7 operations (N^2, N*(N^2), (N^3)^2, (N^6)^2, (N^12)^2, (N^6)*(N^24), N*(N^30)). However, in general finding the minimum number for a given exponent is NP-complete, so in practice square and multiply is presumably what you'd do. Otherwise, great video!

@pikasnoop6552

2 жыл бұрын

The NP-completeness is a common misconception: this is only proven for sets of numbers, not single numbers. In practice I believe a window method is used, for which one precomputes some values so one can "combine" some multiplications.

@Alex_Deam

2 жыл бұрын

@@pikasnoop6552 Thanks for the correction

@Wecoc1

2 жыл бұрын

Efficient exponentiation is a very interesting topic. The minimum number of multiplications required for N is an open problem in mathematics, you can read more about that on OEIS A003313, "Length of shortest addition chain for n".

@Skyb0rg

2 жыл бұрын

That example seems to use more space (you need to remember N^6 until after you finish (N^12)^2). May be the minimum operations in fixed space, where the space is exactly the size of the input string. Also important for cryptographic libraries which shouldn’t be allocating memory dynamically.

@realKlabauterklaus

2 жыл бұрын

If you introduce division as an additional operation, the example of 31 can be reduced to 6 operations: SSSSSD

I read binary numbers left to right by starting at 1, doubling for each bit, and adding 1 if the bit was a 1. Very cool to see this pattern coming up in exponents

I love how entertaining the video is given that I already know what the answer is and have used this quite a lot

I love the step-by-step simplistic explanations you give and the focus on the core concepts. Thanks Mike! bloody champion! Peace and Love from Perth Australia!✌❤✌

I always liked calculating that recursively. For example, 2^6 is (2^3)*(2^3), 2^3 is (2^2)*(2^1) and 2^2 is (2^1)*(2^1). It's extremely simple to code it too. Here's the algorithm that performs the calculation: 1) If exponent is zero, return 1 2) Divide exponent by two, and save both the quotient and the remainder 3) Call algorithm recursively with (exponent = quotient) and save the result 4) If remainder is zero, return result*result 5) If remainder is one, return result*result*base

@canaDavid1

Жыл бұрын

Unless you cache the results, this is no faster than multiplying one-by-one (probably slower because of recursion overhead)

@longlostwraith5106

Жыл бұрын

@@canaDavid1 I don't think you appreciate the difference between O(N) and O(logN).

@schwingedeshaehers

Жыл бұрын

@@longlostwraith5106 you have O(2^log(N)) so O(N)

@longlostwraith5106

Жыл бұрын

@@schwingedeshaehers How, exactly? Are you taking the division into account?

@schwingedeshaehers

Жыл бұрын

@@longlostwraith5106 you have log n layers, but these layer get more and more calculations each level. And they get an exponential growth until the log n barrier from the amount of layers

This was fascinating, so simple and intuitive once explained but so powerful

This is the coolest maths/CS video I've seen in a long time. Wow!

Fantastic! I watched the same Numberphile video and did the high power mod p calculation on my calculator. And during the process I realised that to get the right number of squares, you turn the power into its binary number and then square the same number of times as the power of two. (And mod every time the answer is bigger than 747). I even checked it by finding the nearest actual primes, which are 743 and 751. Perfect 1s for both!

Always wondered how the key reading timing/power attacks worked, that makes a lot of sense, cheers!

Dude, you’re such a fun guy to listen to. Keep it up, cheers!

This video was a lovely reminder of my time spent with number theorists in college, cryptography is so damn fascinating

This is also called "exponentiation by squaring" and it's super useful in many cases. One quick example is in computing the nth Fibonacci number using the 2x2 matrix formula, where one raises a matrix to the nth power. But using this method, the number of multiplications is greatly reduced. There is also a closed form expression using a power of the golden ratio but that requires a lot of numerical precision for large n.

Thank you for this video. One of the most interesting things I've ever done in school, and I'd almost forgotten about it.

You Sir saved my life before the exam, I can't thank you enough.

what a coincidence, i started studying RSA and y'all put out this banger, thanks Mike and Sean

I LOVE this type of content !!!! Thanks a million for making and sharing :)

This is just mind-blowing! Awesome video!

I am currently purchasing master degree in cybersecurity and this guy summerize a 2h of lectures in literally 17min ;)

@QuantumHistorian

2 жыл бұрын

Why are you purchasing a degree? Maybe do it somewhere with better teaching then?

@ait-gacemnabil9181

2 жыл бұрын

@@QuantumHistorian he probably meant pursuing

@johningham1880

2 жыл бұрын

I’m afraid that is the model for university education these days

@jkye_314

2 жыл бұрын

@@ait-gacemnabil9181yeah, you right. but, in some sense, it means actually a business activities for university.

@saiprasad8078

2 жыл бұрын

In a way, he is right. Nowadays everything needs to be purchased -- even knowledge.

I know it was touched on toward the end of the video but I think a part II to this video where Dr. Pounds could go into a specific application example where this is used. Can always use more videos with him!

I love the idea of solving a complicated problem by solving a lot of simpler problems. Genius!

i love the channel. the slowness of the math demonstrations made me itchy!

I did the 3^45 mod 7 in my head fairly simply. 3 and 7 are coprime, so you know that 3 will cycle through all 7 numbers. Then we can do 3^42 * 3^3 mod 7, which is just 1*3^3 or 27 mod 7 which is 6. Still a very useful algorithm though

@thenewnew1997

2 жыл бұрын

Well, the algorithm you use is efficient for human, unfortunately computers don't see the same thing as us and know instinctively to do it, and it is just one particular case, this algorithm allows to be applied on all case scenario with the complexity of O(2*floor(log2(n)) +1) (worst case scenario, so big O) which n is the exponent of the number, so very efficient in terms of complexity. Anyways the method you use is very useful too, just for humans, not pc

@SimonBuchanNz

2 жыл бұрын

In encryption, properties like this are what makes the selection of values so necessary. In this case, the modulo value is generally thousands of bits, while the base is either 3 or 65537 (and the exponent is the message and must be less than the modulo)

You guys and numberphile my 2 favorite channels

Excellent video! Alternative summarised explanation: exponentiation in a sense "converts" addition to multiplication (see 3Blue1Brown's excellent intro to group theory and e^(iπ) = -1 for an exploration of this). The algorithm for converting a bitstring to a number (or equivalently, the binary representation of a number to its decimal representation) is to start with zero and read the number from left to right, doubling when you see a new digit, and then adding the value of that digit (i.e. add noting if it's "0", or add 1 / increment if it's "1"). For example, the binary number 101110101 is equal to decimal 373, as follows, reading the digits of the binary representation from left to right: • Start with 0. • Read a digit, "1": double, then increment, giving 1. • Read "0": double, giving 2. • Read "1": double, then increment, giving 5. • Read "1": double, then increment, giving 11. • Read "1": double, then increment, giving 23. • Read "0": double, giving 46. • Read "1": double, then increment, giving 93. • Read "0": double, giving 186. • Read "1": double, then increment, giving 373. The square and multiply algorithm just starts off with the base of the exponent (i.e. 23 as in the video) rather than 0, and replaces each doubling operation with a squaring, and each increment operation with a multiplication by the base. That is, exponentiation with base 23 has converted addition of 1 into multiplication by the base, 23. Likewise, doubling a number (which is the same as adding a number to itself) has been converting into squaring a number (which is the same as multiplying a number by itself).

The last minute was spot on - avoiding side attacks!

I literally submitted my rsa cryptography coursework in two weeks ago. This is all fresh in my mind. I'd love to see this go to the next step.

@sugarsugar4410

2 жыл бұрын

Whats the next step?

Saw an implementation of this in a programming tutorial video but they just rushed over the details. Computerphile does a wonderful job at filling this gap (as always I might add!)

Truly interesting lesson, just studied this at school!

Interesting algorithm and great video as usual

binary to decimal: go left to right, start from 0 and double if it's a 0 and double and add one if it's a 1. e.g. for 101010 you do 0 -> 1 -> 2 -> 5 -> 10 -> 21 -> 42. so 101010 = 42. decimal to binary: halve your number rounding down until you reach 1, e.g. 42 -> 21 -> 10 -> 5 -> 2 -> 1. now go backwards through this sequence and put a 1 if it's odd and put a 0 if it's even. so 42 = 101010.

I remember using this algorithm for a competitive programming question on one of the codechef's monthly contests, didn't know it had a name.

@alicebobson2868

2 жыл бұрын

i did this aswell in codeforces

You can do multiplication this way, too (by doubling & adding). Very useful on CPUs that can only do addition.

@trejkaz

2 жыл бұрын

This is also how I've seen multiplication done on mechanical calculators.

@PvblivsAelivs

2 жыл бұрын

You can. But it's faster to subtract squares. You have to build the table first. But you don't need multiplies to do it.

@canaDavid1

Жыл бұрын

@@PvblivsAelivs this depends on the speed of memory accesses, and how much memory space is available. But yes, table lookups are usually faster.

Great video, thanks! He belongs in Numberphile videos too

1) You rock, thank you for making world better. 2) Focus fail hurts eyes.

Amazing each time a watch your videos

You could explain this much more easily and without binary like this: You take the exponents and apply two rules until you get to 1: - if it's odd, subtract one - if it's even, divide by two Then you just do the squares/multiplies in reverse order of these operations.

@Loldemord

2 жыл бұрын

This is basically how you create the Binary Number out of the 10-base ^^ So its the same

@deanjohnson8233

2 жыл бұрын

That might explain it, but that is not how it would be programmed efficiently

@user-vn9ld2ce1s

2 жыл бұрын

@@Loldemord True

@user-vn9ld2ce1s

2 жыл бұрын

@@deanjohnson8233 That's probably true, if we're talking about something like assembly (those bit shifts are single opcodes, aren't they?), but if i were doing this is in python, it probably wouldn't matter...

@deanjohnson8233

2 жыл бұрын

@@user-vn9ld2ce1s you would implement it like this in assembly, c, c++, go, rust, c#, Java and many more. Bit shifting is not a rare and unusual thing. In python it would be strange because python does not have fixed numeric sizes. Using bitwise operations on something like that can easily lead to the wrong result if you don’t carefully study what Python does in various cases. Also, this video was about how to efficiently do this math. If you are concerned with the efficiency of math operations, you probably aren’t going to be using python.

The one involving modulo 7 can be done relatively easily- as it’s prime we know 3^6 is congruent to 1 mod 7 ( Fermat’s little theorem ), then do 45 mod 6 and hence get to (3^6)^7*(3^3) mod 7 which is (1)^7*(3^3) mod 7 which is of course 6 mod 7.

I love this (semi-)collaboration. You are computerphile version of Matt Parker in any way.

@benwisey

2 жыл бұрын

Matt Parker and Mike Pound. MP=MP.

This was fantastic!

We call it binary exponent algorithm For example 3^10 =? we write its power in binary 10 = 1010 The bits which are set will be included in the final ans as we can calculate all exponent which are powers of two very quickly. 3^10= 3^8 * 3^2

thank you guys🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻, it was really insightful. ♥️

Waiting for those follow-up videos!

So, it turns out Square and Multiply on its own is not the greatest scheme for cryptography, because it lends itself to side channel attacks (timing and power usage). The way this is addressed is through a Montgomery Ladder, where every square operation is performed, and every multiply is performed, but the bit that determines whether it's a simple square or a multiplication actually determines where the output is placed. If it's intended to be used, it goes in the "correct" output location and mixed usefully in with the result. If it's not, it goes into an incorrect output location, and mixed in with all the other side-effect garbage from the function. This results in the power draw and time being constant, which defeats those side-channel attacks.

MIND BLOWING !

god Dr Pound is so good at explaining things

It's true that using this algorithm on the private key exponent is more expensive than the specially chosen public exponent. (2048 bit exponent -> 4096 multiplies). However since for the RSA algorithm, the private key holder knows the factors used for the key, an algorithm based on the Chinese Remainder Theorem can reduce the cost of the private key operations.

@666Tomato666

2 жыл бұрын

yes, but CRT reduces the cost by a factor of about 3, so the private key operations are still slower than the public key operations which need to calculate power by a 16 bit number

This man is a legend

cool trick, didn't realize that relation i love this series

Nice use of symmetry and multiplication.

Amazing video, I almost want to incorportate it to my program.

I always did square and multiply from the last significant bit first. In C, this is: double pow(double x, int exp) { unsigned int e = (exp >= 0) ? exp : -exp; double result = 1.0; while (e) { if (e & 1) { result *= x; } x *= x; e >>= 1; } if (exp return (1.0 / result); return (result); } When I do it on paper by hand, I just calculate all squares first. Then I multiply every result corresponding to a 1 bit, starting from the least significant bit. Of course, the order in which I multiply does not matter, but it is how I always did it.

This guy should have his own channel lol great stuff tho love it

Such a cool method! The very fact that you can calculate 3^45 mod 7 on paper in a few minutes is awesome considering 3^45 has 22 digits!

@trejkaz

2 жыл бұрын

You can do it faster. For instance, observe that 3^6 mod 7 is 1. So 3^45 mod 7 is going to be the same as 3^3 mod 7, which is 6.

@JivanPal

2 жыл бұрын

@@trejkaz That depends on you knowing the totient of the modulus / order of the multiplicative group, which is hard if you don't know the prime factorisation of the modulus.

@trejkaz

2 жыл бұрын

@@JivanPal I don't know much about groups at all and didn't really use any group theory to do that solution, just normal modular arithmetic. Although, in the video he did say that the modulus is usually prime for these examples, so I don't think I'd have too much trouble determining the factors either.

@JivanPal

2 жыл бұрын

@@trejkaz It depends. The hardness of that factorisation problem is what gives RSA its security. The totient function, denoted φ(x), counts how many numbers less than x are coprime to x. It is such that φ(p) = p-1 where _p_ is any prime, and φ(ab) = φ(a)·φ(b) where _a_ and _b_ are any two integers. The encryptor's/signer's secret is a pair of large primes, _p_ and _q,_ that serve as the private key, and the public knowledge that serves as the public key is their product, _n_ = _pq._ Thus, the encryptor/signer is always dealing with _p_ and _q,_ whereas the decryptor/verifier is always dealing with _n,_ whose prime factorisation he doesn't know. Without that knowledge, computing φ(n) is hard; with that knowledge, it is trivial: φ(n) = (p-1)(q-1). If he could figure out the prime factorisation, the encryption scheme is broken, precisely because he then knows φ(n) and can thus quickly compute these modular exponentials we're interested in: g^x mod n = g^[x mod φ(n)] mod n.

@thenewnew1997

2 жыл бұрын

@@trejkaz can you generalized this method for all case scenario for computers? This method allows to be generalized for every case scenario with complexity of O(2*floor(log2(n))+1) and it is very efficient already (n being the exponent of the number to verify). Since I'm at it I'll also remind you that computer don't have instinct or intelligence like us

Huh. I was using a similar but substantially slower method. Good to know it can be improved upon.

Mike Pound - Always good value 8-)

fooking genius mate

This is really cool! I'm glad that i learned about binary numbers, because I wouldn't have been able to understand any of this otherwise.

This was a fascinating video even if the algorithm was rather obvious.

Crazy impressive

nice how you built in the eyes-glazing-over effect into the video so my eyes didn't have to this time like they have in some other videos (because things are complex, not because they're boring) :D

12:55 you can work backwards: if it's odd, subtract 1, if it's even, devide by 2 ;)

That's a wicked smart algorithm.

math is amazing, especially if used in the correct way ;-) you guys are also AMAZING! ;)

Thanks man. ❤️❤️

This is really clever

cool video! cool algorithm!

Basically Russian Multiplication (covered by Johnny Ball on Numberphile), but square and multiply instead of double and add. Surprised that wasn't mentioned.

@JivanPal

2 жыл бұрын

Indeed! That is the basis of a common efficient algorithm for converting string representations of integers expressed in base _n_ into actual integer datatypes, too, e.g. for decimal in C: char* input_string = "285657"; int result = 0; for (char* c = input_string; c != NULL; c++) { result += *c - '0'; result *= 10; } Or for capitalised hexadecimal: char* input_string = "45BD9"; int result = 0; for (char* c = input_string; c != NULL; c++) { result += isdigit(*c) ? *c - '0' : 10 + *c - 'A'; result *= 16; }

Very helpful.

Are you going to make a followup talking about addition chains?

thank you!!

I didn't learn this one at school. It's gorgeous! Thank you.

yeah! in my assembly class, when we had to program, there is no multiplication operator, so you'd have to shift the bits of the binary value in the registers to actually multiply two numbers. Don't even get me started with bringing in value into registers, and these values can't be stored in just any registers... and then pulling the value out.. storing elsewhere... god bless ..

the timing/power thing at the end is called a side channel attack

Yet again I see 65537 which coincidentally is my favourite number too! It's the 17 bit big brother of 257.

Does this represent the smallest number of steps for any given exponent?

Is there a video about modulo math commuting for both addition and multiplication? I don't remember one, and it seems to be explicitly required here.

@JivanPal

2 жыл бұрын

What do you mean by "commuting" here?

A cool video and topic but I would like to nit pic the camera placement when Dr Mike writes on his paper. Surely the camera could have been on his left side?

5:24 - cleaner explanation to convert 45 -> 101101 -> 32 + 8 + 4 + 1.

@NoNameAtAll2

2 жыл бұрын

that's backward of this algorithm you did calculation of powers of 2 and multiply them in the video 101101 -> (((((1)*2+0)*2+1)*2+1)*2+0)*2+1

@JivanPal

2 жыл бұрын

@@NoNameAtAll2 Or in postfix notation to avoid all those parentheses: 1 2× 0+ 2× 1+ 2× 1+ 2× 0+ 2× 1+.

@NoNameAtAll2

2 жыл бұрын

@@JivanPal why not prefix then? + * + * + * + * + * 1 2 0 2 1 2 1 2 0 2 1 :)

math rules, i love these kind of tricks

Being half asleep when watching this, for a moment when he was going over all the steps I thought I was nodding off, but nope, it was just the camera. Perhaps get the camera some coffee in the future.

For people not understanding binary, here is a way to do it without using binary: 1)Let the power be x, 2a)If x is odd subtract 1 from it and write M(multiply) on a paper 2b)If x is even half it and write S(square) on paper 3) with the new x(either half or one less), repeat step 1) until x becomes 1 4) if x is 1, do the steps shown in the video, but start from the bottom of the list For example: For 373, M 372 S 186 S 93 M 92 S 46 S 23 M 22 S 11 M 10 S 5 M 4 S 2 S 1 Then the correct step would be S S M S M S M S S M S S M(this is just the order of operations, you would still have to do all the mod and other things) Note: S=Square; M=Multiply

This could be used to compress files, it would need serious modifications, but it has potential

So is modulo distributive over multiplication? Is that why we can keep the numbers small?

I always wondered how we dealt with such enormous numbers

A similar algorithm can be applied for divisions.

Perfect timing. I need to learn this for an exam (no calculators allowed). Thanks!

Could you make a video about opaque.

There are a couple of Project Euler questions that this will help solve.

What an interesting algorithm

Square is ab it limit Multiplication, while Multiplication is a bit like addition. Just in the amount it will change the overall result.

A comment that i've liked "This man forgot things about computers more than what i will ever learn"

Mike Pound for Numberphile video, please.

FINALLY SOMETHING I CAN APPLY MY MATH III KNOWLEDGE ON.