simple math problem: Find the nearest multiple of a number

[Saeros]

This is probably a simple math problem, but i suck at math .

Given number x, where x is between 0 and 255, I need to find the nearest multiple of y, where y is a power of 2 between 0 and 128, to x.

I'm not sure if i described that properly, so I'll give an example. Suppose I have number 87, and i need to find the nearest multiple of 16 thereto. In this case, the answer would be 80; 87/16=5.4375 and (5.4375-0.4375)*16=80.

Does anybody know of any way by which to do this calculation really fast? I only have a couple of seconds to figure it out, and i won't have access to a calculator .

Bonus points awarded to anyone who can guess what this is for

 

[EyeSeeCold]

http://intjforum.com/

 

[Saeros]

http://intjforum.com/

Very helpful. Thank you.

 

[ApostateAbe]

Is it for cheating on a test? For homework? For the homework of a cute girl you want to impress? It doesn't seem to be an easy problem. I imagine I could figure this out with a little research and algebra in MATLAB or something. Do you think it would be worth it for you? I know it wouldn't be worth anything for me except another way to fill my time and a little praise from people I don't know on the Internet.

 

[Saeros]

Is it for cheating on a test? For homework? For the homework of a cute girl you want to impress? It doesn't seem to be an easy problem. I imagine I could figure this out with a little research and algebra in MATLAB or something. Do you think it would be worth it for you? I know it wouldn't be worth anything for me except another way to fill my time and a little praise from people I don't know on the Internet.

I'll need to be able to do this to answer a lot of questions on a certification exam that I'll be taking soon, so it's fairly important to me.

 

[ApostateAbe]

OK, I was thinking too much like a programmer when I first thought about it. You won't have access to a calculator, so it just looks to be a test on how quickly you can do simple math on the fly. If you must, you may use the formula: int((y+x-1)/x)*x (where "int" is a function that rounds down to the nearest integer), but I wouldn't. You won't have access to a goddamn calculator. Get back to the elementary school basics where the teacher wouldn't let you use a calculator. Pick two random numbers and do a problem. Then pick two more random numbers and do it again.

 

[Saeros]

OK, I was thinking too much like a programmer when I first thought about it. You won't have access to a calculator, so it just looks to be a test on how quickly you can do simple math on the fly. If you must, you may use the formula: int((y+x-1)/x)*x (where "int" is a function that rounds down to the nearest integer), but I wouldn't. You won't have access to a goddamn calculator. Get back to the elementary school basics where the teacher wouldn't let you use a calculator. Pick two random numbers and do a problem. Then pick two more random numbers and do it again.

Yea, that seems like the only way to do it. Thanks.

 

[echoplex]

Damn, I tried a bunch of stuff hoping I'd stumble upon some ingenious solution, lulz, but nothing I tried worked consistently. I would just practice multiplying large numbers in your head. Since none of them will be any higher 128, it shouldn't be too hard, I think.

For instance, I did one where x=224 and y=72. So, you count by 72 until you come to a number less-than-but-not-far-from 224. 72, 144, 216...bingo, 216 has to be the answer. That's one of the easier ones though.

Also, if I understood your description, some problems will have two answers, right? For instance, in your example, if x instead = 88, then both 80 and 96 would be acceptable answers. Or did you mean the lowest nearest multiple?

Wait, if y only = powers of 2, then you need to simply practice multiplying those numbers: 2, 4, 8, 16, 32, 64, 128.

 

[Melllvar]

If you must, you may use the formula: int((y+x-1)/x)*x (where "int" is a function that rounds down to the nearest integer)

Guessing is unreliable, and that equation isn't particularly complicated. You don't have to actually work out the division, just guess the multiple of x that will get closest to (y+x-1) without going over.

For example, if y+x-1 = 55, and x = 7, the nearest multiples of x are 49 and 56, but 56 is more than 55 so go with 49 (which corresponds to 7). So int((y+x-1)/x) = 7 (since you rounded down, if you'd rounded to the nearest it would have been 8, since 56 is closer to 55 than 49 is).

y+x-1 = 32, and x = 9, the nearest multiple without going over is 27, which you get by x * 3, so int(y+x-1)/x = 3.

Then just multiply your result by x and you have the answer you're looking for. Except I didn't bother checking that equation, I'm just assuming ApostateAbe's correct about it.

In general I find it's easier to just guess the nearest multiple without going over and count up to the actual number to get the remainder, rather than actually doing long division. Even if the numbers are very different, like 7 and 536, just keep counting up by multiples of 10: 7 * 50 = 350, 7 * 10 = 70, and 350 + 70 + 70 = 490 (remainder 46), 7 * 6 = 42, so 536/7 = 76 (50 + 10 + 10 + 6) with a remainder of 4. It's way easier than writing out the long division every time.

Edit: Actually, I hadn't fully read your OP. It seems I'm basically describing the same problem you're supposed to solve. In any case, the last paragraph is probably the most relevant, since that basically shows how to count up quickly and find the largest multiple without going over.

 

[Artsu Tharaz]

If you can't do this quickly in your head, just learn the multiples of powers of two :S

Also why:

http://intjforum.com/

?

 

[The Gopher]

Because INTJs just love work.

 

[Latro]

While there is probably a formula for this, especially when you're constrained to powers of 2, bisection will probably work fine. Your function, for this example, is f(n) = 16*n, so the bisection goes like:
f(1)-16--some stupid big error
f(15)-240--some stupid big error
f(8)--128--error of +41
f(5)--80--error of -7
f(6)--96--error of +16

Then since the function is strictly increasing in n, the solution is 80.

Again though, bisection is pretty naive, so there's probably a better way.

Edit: And yeah, there is. If q(y,x) is the quotient when y is divided by x, and r(y,x) is the remainder when y is divided by x, then the solution will always be one of:
(q-1)*x, q*x, (q+1)*x.

Figure out which one by finding the smallest of |r-x|,|r|,|r+x|.

 

[James Black]

Best way to do it is to learn the powers of 2 in the given range (aren't many, not difficult)
Then, I believe that your answer will always be the sum of some powers of 2.

In the original question, you have 87, and 16. Your powers of two you can use are now between 16 and 128. That gives you 128, 64, 32, 16. Take 128. Its higher than 87, can't be used. 64 can, its the number you want to use. 64 + 32? Too high. 64 + 16? 80. Done. Its important to realize that even if the number was 88, not 87 (at which point 80+8 would seem the right answer) the answer is still 80: the reason you stop at 16, regardless, is because it wouldn't be a multiple of 16, it'd be a multiple of 8. Given the nature of multiples of 2, no combination of numbers below 2^x will ever add up to anything more than 2^x - 1.

Say you have 130 and 32. You now have 128, 64, and 32 to find the answer. Start with 128. Well, thats an easy problem.

Also, unless I'm mistaken, given that 2^(x+1) is 2^x + 2^x, you'll never need to add the same power of two twice for your sum/answer.

Given some practice its not hard. Its easy to see your answer to the above question is 128, unless your power of 2 is 1 or 2: But if your power of 2 is 1 or 2, you shouldn't be spending too much time trying to figure it out.


Edit: I kept writing x^2, instead of 2^x.

 

[EyeSeeCold]

INTJs are better at math.

 

[James Black]

Better? No way. More willing to try? Perhaps.

Also, after reviewing the question, I believe the method I suggested may be what was intended: if x is between 0 and 255, that makes it between 0 and (2^8) - 1, and if y is between 0 and 128, that makes it between 0 and (2^7). Therefore, the nearest multiple of y near x will always work out as the sum of multiples of 2 below 2^8 working down from 2^7 to 2^n. (2^n = y)

 

[Artsu Tharaz]

INTJs are better at math.

Do you have any verification for this? I thought maths was more of an INTP thing, based on being able to build abstract, efficient systems of thought (Ti) and see how these ideas relate to a wide range of contexts (Ne). Of course, I'm going to see this as the way maths is done since this is the way I do maths, but maybe INTJs can do it just as well, if not better, perhaps being better at "seeing" the solution, and building up the steps to get to it.

So yeah, any thoughts or evidence to differences in mathematical ability and technique between the two groups, and the type of maths problems each would excel in?

 

[marcus73x]

Try this forum.

http://www.firewall.cx/ftopict-295.html

Seems like you're a soon-to-be CCNA?

 

[ThreeM]

This is a simple CS problem if i understand your problem right (with a little interpretation):
you have 0-255 (256 total bits basically because in our number system 0 counts unless otherwise noted)
2^8 = 256
an example that makes it easy to remember is that it goes in the same order as the original console games back in the day
you will have to remember 2^2 =4 on your own but after that...
Atari/NES 2^3 = 8 bit
SNES 2^4 bits = 16 bit
Sega Genisis 2^5 = 32 bit
N64/Sony PS 2^6 = 64 bit
etc etc

Remember Einstein was an INTP your intuition will serve you well in math.

Then again I'm still trying to figure out if I am an INTP or an INTJ because I display a large proportion of attributes from both... I did the test online listed in this forum and it showed INTP but the J-P part wasn't off to the P side as much as the others to provide a definitive answer... so I'm still confused.

 

[Stoic Beverage]

Bonus points awarded to anyone who can guess what this is for

I'll need to be able to do this to answer a lot of questions on a certification exam that I'll be taking soon, so it's fairly important to me.

I'm guessing this is for a certification exam that you'll be taking soon.

Now, where are my points?

 

[Geminii]

Take the binary representation of the given integer, change the log2(power of two number given) digits on the right to zeroes, change back to decimal notation. That's the lower multiple of the power of two number. If it's more than half that power-of-two number away from the given integer, then you want the upper multiple, which you can get simply by adding the power of two number.

Example:
Integer: 87
Power of two number: 16

Binary representation of 87: 01010111
Log2 of 16 = 4
Change rightmost 4 digits of 87 to zeroes: 01010000
Change back to decimal: 80
Is 87 more than half of 16 away from 80? No
Therefore 80 is the closest multiple
(Otherwise it would be 80+16=96)


However, the fast way to do it is simply to know tricks for figuring out local sequences of power-of-two multiples between 0 and 255.

For example:
Power-of-two: 2
Trick: Even numbers are divisible by two.

Power-of-two: 4
Trick: If the last two digits form a number which is divisible by 4, the whole number is.
Example: 36, 136, and 236 are all divisible by 4.

Power-of-two: 8
Trick: If the last two digits form a number which is divisible by 8, the whole number is - for even hundreds digits. Otherwise, add/subtract 4.
Example: 32 and 232 are divisible by 8, and so is 136 (added 4).

Power-of-two: 16
Trick: 96 and 192 are both divisible by 16. So for numbers under 100, just memorise them (16, 32, 48, 64, 80, 96). For multiples over 100, just subtract 4 from the last two digits (112, 128, 144, 160, 176, 192). For multiples over 200, subtract 4 twice (208, 224, 240). Or just memorize them - there are only 15 (not counting zero itself).

Alternative: Memorize the first five (16, 32, 48, 64, 80). Chop up your given integer into chunks of 80 and work from there.
Example: The integer 201.
Count: 80...160...240.
201= 160 (an 80-chunk) + 41.
41 is closer to 48 (a multiple) than 32 (a multiple), so the closest multiple is 160+48, or 208.

Power-of-two: 32
Trick: Memorization. 32, 64, 96, 128, 160, 192, 224.

Power-of-two: 64
Trick: Memorization of three numbers. 64, 128, 192

Power-of-two: 128
Trick: There's just the one nonzero number.

Of the lot, the fiddliest one to remember is often 32. Sometimes it's easier just to memorize the sequence for 64 and then interpolate on the fly as needed.

Another way is to do a lot of work with IPv4 subnetting. You'll find the same numbers turning up over and over and over, and they tend to sink into your brain.