|
Googling "truncated multiplication" only gets me a bunch of complicated-sounding journal articles. Any suggestions on where to learn about it?
|
#
?
Mar 18, 2012 03:55
|
|
|
|
| # ? Apr 29, 2024 01:00 |
|
|
It's not truncating multiplication, it is called modular exponentiation First lets work with smaller numbers so you can see how it works Say you have 31**23. First you have to understand that 31^(a+b) is equivalent to 31^a * 31^b, you can further break it down into different factors: 31^(a+b+c) = 31^a*31^b*31^c and so on. To get the first n digits of a number, you take the number and modulo by 10^n. So 12345678 % 10^4 will get you the first four digits of the number: 5678. Therefore you can apply this to the problem by breaking the problem down into smaller problems that are easier to evaluate. If you wanted to take the first 4 digits of 31**23, one way you can do this is by splitting the factors into smaller equivalents. Since it is easy algorithmically to break down a number into powers of 2 (aka binary numbers) we can write 31^23 as 31^1 * 31^2 * 31^4 * 31^16. Now since 31^23 % 10^4 will get us the first 4 digits of 31^23, by the powers of modulo we can apply this to the smaller problem, specifically 31^23 % 10000 ~= (31^1 * 31^2 * 31^4 * 31^16) % 10000 However if we apply this to bigger numbers we still run into overflow problems when we move into larger numbers. But since we only care about the first n digits we modulo each number by 10^n to give us accurate results up to the nth digit. So (31^1%10000)*(31^2%10000)*(31^4%10000)*(31^16%10000) = 889606955391, but since only the first n digits are accurate (and the only ones we actually want), we mod the result by 10^n again, which leaves us with 5391. 31^23 = 20013311644049280264138724244295391 % 10^4 ~= 5391. Edit: Spacing. Strong Sauce fucked around with this message at 06:37 on Mar 18, 2012 |
|
#
?
Mar 18, 2012 06:28
|
|
|
Thanks for the replies guys, the results come in soon, so we'll see how important it was. Also thanks for explaining that Strong Sauce, I don't think I could have pieced that together under pressure, but I think your explanation is what I *wanted* to go for. I think I was too afraid of the dead phone silence I would need to actually figure out how.
|
|
#
?
Mar 18, 2012 08:08
|
|
|
Strong Sauce posted:It's not truncating multiplication, it is called modular exponentiation No it's called modular multiplication.
|
|
#
?
Mar 18, 2012 09:50
|
|
|
theratking posted:Thanks for the replies guys, the results come in soon, so we'll see how important it was.
|
|
#
?
Mar 18, 2012 10:28
|
|
|
pigdog posted:It is still wanky bullshit and irrelevant in the great majority of programming jobs. Unless indeed your tasks are math heavy such as rolling your own cryptography, then I for most programming positions it can't see the immediate relevance. It might make sense to put a candidate in a room with a connection to Google and let them figure it out as a test of problem-solving skills. But not to have a solution immediately ready shouldn't be a disqualifier, unless you're perhaps explicitly expected to do a lot of math. Do expect interviews to just be full of questions you know how to answer? The only way to accurately measure the quality of a candidate is to ask a wide variety of questions and to push up the difficulty until you find the sort of questions he has trouble with. Also the point of interviewing programmers is not to see if he has the skills he'll need for the job, it's to see if he will have the skills he needs for the job after a short period of time, and that's a combination of measuring skills he has and also general intelligence, and the ability to cope with unfamiliar situations. Not every problem you face in programming is one that you have solved before. What do you expect people to do when they run into something they don't know the answer to? Part of the job as a programmer is to be able to figure out new algorithms for new situations. For what it's worth, that math problem is the sort of thing we'd expect any interviewee (that we'd be willing to hire) to be able to answer, not necessarily immediately, and that's not based on the expectation that they already know how to do it! To be fair a lot of people would just get that question easily because they've done it before or because they have a light amount of mathematical inclination. These are valuable features in a candidate! (Seriously, what kind of slime mold has never wondered how RSA works and then wondered how you could possibly compute efficiently? Who hasn't played around with the cycles that pop up when you iterate modular multiplication?) shrughes fucked around with this message at 10:41 on Mar 18, 2012 |
|
#
?
Mar 18, 2012 10:34
|
|
|
quote:For what it's worth, that math problem is the sort of thing we'd expect any interviewee (that we'd be willing to hire) to be able to answer, not necessarily immediately, and that's not based on the expectation that they already know how to do it! Personally, I would have truthfully answered "I can see that the most straightforward way of calculating 3^12345678 is impossible, but I'm sure there's a more optimal mathematical solution. I'll consult someone with better knowledge of math for an effective way to solve this problem, and implement it". The question isn't in the domain of programming, it's in the domain of math. What if the (math) problem was twice or thrice as difficult and certainly not in the realm you'd expect from the average software developer? Sure, the dev might stumble upon a solution eventually, but in real life with actual problems, a programmer mucking about and making assumptions in a domain they aren't quite familiar with, is where all sorts of bugs and inefficiencies come from. In a real project, where there isn't an interviewer with a notepad looking over their shoulder, a dev might actually try and calculate that 3^12345678. Perhaps even be successful, if the value was somewhat less astronomical. The solution is to consult someone with the necessary domain knowledge and apply their knowledge for an optimal solution. If the developer in that position himself is presumed to be that person with the necessary math knowledge in the project, then sure, that's a valid interview question. pigdog fucked around with this message at 13:29 on Mar 18, 2012 |
|
#
?
Mar 18, 2012 13:27
|
|
|
pigdog posted:Given it was a phone interview, I did get the impression they were expecting an answer. That's true, but it's more a question of whether or not you really made it through a CS degree. I don't know how anyone could've made it through a CS degree without knowing the modulus stuff cold, it's an operator I virtually never used outside of intro to CS and cryptography.
|
|
#
?
Mar 18, 2012 13:52
|
|
|
Sorry but I think you are full of poo poo. Very rarely will you encounter a unique problem that hasn't been solved before. Your first reaction should be determining if it's a solved problem and seeing if the solution fits your needs. I've seen way to many square wheels forged out of ignorance that a simple google search would have resolved. Also before you ask about RSA you should ask how many programmers know about public/private key encryption and the problems it solves. There's way too much complacency in our industry.
|
|
#
?
Mar 18, 2012 13:55
|
|
|
Yeah just for the record my interviewer definitely was expecting an answer, and no bullshitty "I would consult an expert" answer either. I tried a few times to go that route and I could tell he wasn't warming up. The language barrier could have been a factor, or the fact that he just wasn't a very good interviewer.
|
|
#
?
Mar 18, 2012 17:57
|
|
|
"I would consult an expert" is not a bullshitty answer, it's the sensible course of action for situations like these, when you know some better solution must exist, but you're not quite sure. If a candidate can solve a problem such as this on his own, that's great and good for him. If however the candidate does receive a problem (such as this) which he can't well make sense of on his own, then consulting someone with better domain knowledge is, in my opinion, the right answer. Even better than just looking it up on Google, because the expect may well know the context better. It's much better to consult someone who knows what he's talking about, rather than making assumptions on a field you're not completely familiar with - because such assumptions are THE cesspool from whence all sorts of bugs are spawned from. Being clear on the requirements is in the domain of what being a good developer is about. In the grand scheme of things, it doesn't matter if the developer arrives to the right course of action by himself or spending a bit of the expert's time; it matters that the solution is actually correct and what is needed. Is the interviewer testing whether the interviewee remembers his math classes, or whether he is approaching a problem outside of his domain knowledge the right way? Either way, I do wish you luck. 
pigdog fucked around with this message at 18:46 on Mar 18, 2012 |
|
#
?
Mar 18, 2012 18:44
|
|
|
I do understand it is the right answer "in the real world," but my point was that I could definitely tell this was not the sort of answer he was looking for. Not only is just winging a problem you don't really understand a source of bugs, but also a source of huge blocks of wasted time. When I first started doing web development, I tried doing things the way I knew how without really getting guidance. It turned out I was doing things super slowly, and learning a few simple things (10 min lessons max) sped up production hugely.
|
|
#
?
Mar 18, 2012 18:56
|
|
|
quote:Not only is just winging a problem you don't really understand a source of bugs, but also a source of huge blocks of wasted time.
|
|
#
?
Mar 18, 2012 19:22
|
|
|
That makes sense now. I did basically the same thing on homework in one of our introductory programming classes where we were supposed to implement objects that represented huge integers. We were never really taught that sort of thing, explicitly, though I guess it is kind of easy now that I remember it. Thanks for the explanation, Strong Sauce! Tangentially, I'm pretty sure most people in the class just handled multiplication as repeated addition, which resulted in some ridiculous run times (as in, 45+ minutes) when my friends compared our implementations later.
|
|
#
?
Mar 18, 2012 19:31
|
|
|
It's a bullshit question if the interviewer isn't going to guide you in helping you figure it out. Because at that point it becomes whether you know that exact question or not and not really asking if you have any critical thinking skills. Don't say "I would consult an expert" however since that implies you are not an expert... at anything.
|
|
#
?
Mar 18, 2012 19:46
|
|
|
The anti-intellectualism in this thread is pretty funny. How dare anyone expect you to solve problems you haven't seen before? You encounter a thing you don't know and instead of thinking "hey I learned something today" instead you get angry because how DARE anyone expect you to know that!!
|
|
#
?
Mar 18, 2012 19:57
|
|
|
Nippashish posted:The anti-intellectualism in this thread is pretty funny. It's hardly anti-intellectualism. No one is mad at learning something new. It is annoying though to be asked a very specific question that does not accurately measure your ability as a programmer. While it's fair to ask a tough question to gauge your problem solving skills, it's unreasonable for the interviewer to expect you to solve such a question perfectly.
|
|
#
?
Mar 18, 2012 20:05
|
|
|
Because a programmer being unsure about something, and making assumptions due to poor understanding of a subject, is objectively a bad thing which literally creates bugs, inconsistencies, unexpected behavior, and wastes time fixing all that after the fact. If you don't know <subject> and are expected to solve a <subject> problem, involve an expert. It's cool if the knowledge of a foreign domain spreads - say next time you'd know how to get those 500 last numbers - but whether or not a coder figures it out on his own, hardly makes or breaks a project. Trying to Rambo through alone and coming up with a poor, buggy solution which doesn't work as expected - that very well might. pigdog fucked around with this message at 20:11 on Mar 18, 2012 |
|
#
?
Mar 18, 2012 20:09
|
|
|
Strong Sauce posted:It's a bullshit question if the interviewer isn't going to guide you in helping you figure it out. Because at that point it becomes whether you know that exact question or not and not really asking if you have any critical thinking skills. . . . Huh? Admitting that there's someone out there besides you that understands the subject very well automatically means that you aren't good at anything?
|
|
#
?
Mar 18, 2012 20:24
|
|
|
HondaCivet posted:. . . Huh? Admitting that there's someone out there besides you that understands the subject very well automatically means that you aren't good at anything? When you say the equivalent of "I'd go ask an expert on arithmetic" it sure does, or at least suggests it pretty strongly.
|
|
#
?
Mar 18, 2012 20:40
|
|
|
Nippashish posted:When you say the equivalent of "I'd go ask an expert on arithmetic" it sure does, or at least suggests it pretty strongly. There's nothing wrong with admitting you don't know how to solve a problem. I've been writing software professionally for about 8 years now and I routinely will involve other folks to see if they have different or better solutions than I came up with.
|
|
#
?
Mar 18, 2012 20:43
|
|
|
So do you guys enjoy working with people that say they know how to do things when they actually don't? Or is no one supposed to leave their basement until they know absolutely everything? I am genuinely curious because people that think this way are pretty common and I never know how to deal with them.
|
|
#
?
Mar 18, 2012 21:09
|
|
|
All this jibber-jabber has done a great job of defining the limits of the mediocre programmer.
|
|
#
?
Mar 18, 2012 23:16
|
|
|
shrughes posted:Really being familiar with the behavior and possibility of truncated multiplication is something computer science students should know, considering that's what CPU's do. So you should have all the knowledge needed to solve this problem. Really being familiar with rotational transformations of n-dimensional coordinate systems is something computer science students should know. That doesn't mean it's useful outside of rare edge cases. edit: or that even an excellent, productive programmer would be able to figure it out without recent exposure to the principles. baquerd fucked around with this message at 23:30 on Mar 18, 2012 |
|
#
?
Mar 18, 2012 23:26
|
|
|
pigdog posted:The question isn't in the domain of programming, it's in the domain of math. What if the (math) problem was twice or thrice as difficult and certainly not in the realm you'd expect from the average software developer? We're talking about designing an algorithm here, it's in the domain of programming. pigdog posted:Personally, I would have truthfully answered "I can see that the most straightforward way of calculating 3^12345678 is impossible, but I'm sure there's a more optimal mathematical solution. I'll consult someone with better knowledge of math for an effective way to solve this problem, and implement it". Any good developer would recognize that you can compute 3^n in better than O(n^2) time because the problem is subdividable as it's analogous to a case of folding an associative operation over a list in which the size of partial outputs equals the sum of the sizes of the inputs, which generally turns the O(n^2) left-to-right algorithm to O(n log n). (For example, concatenating a list of small strings, using only a linear-time string + operator, can be done in O(n log n) time.) Anybody who's any good at programming and thus good at algorithms could at least see it that way and see the sub-dividing solution that computes 3^12345678 efficiently. (You'd also expect them to know that multiplication takes under O(n log(n) log(log(n))) time so that we actually have an improvement, this is just the sort of lore that good developers know.) Of course really they'd recognize that you can always compute the ceil(n/2) subproblem from the floor(n/2) subproblem efficiently here, you just have to multiply by 3, if they're not the same. And good developers will also be able to see that since the last five hundred digits of the result of a multiplication depend only on the last five hundred digits of the input, the rest of the number can be thrown out at intermediate steps. This brings the computation cost to 500log(500)log(log(500)) * log(n), so to speak, which is easily small enough to compute. The least likely knowledge that a good programmer would have here is knowing that multiplication can be done in sub-O(n^2) time. They should still be able to get the cost down to 500^2 * log(n) time, which is still more than cheap enough. People who can't do this sort of reasoning to solve problems are not good software developers, and it's completely reasonable for companies to avoid them. This is core data structures & algorithms technique. No domain-specific knowledge other than what you see when you learned how to do multiplication by hand is needed. shrughes fucked around with this message at 23:48 on Mar 18, 2012 |
|
#
?
Mar 18, 2012 23:38
|
|
|
quote:People who can't do this sort of reasoning to solve problems are not good software developers, and it's completely reasonable for companies to avoid them. The really professional answer to a task such as "write some code that gets the last 500 numbers for values the likes of 3^12345678" can only be a suspicious look and a "Why?", because such values are never encountered in the real world and their answer would almost inevitably include something stupid such as rolling our own cryptography.
|
|
#
?
Mar 18, 2012 23:49
|
|
|
pigdog posted:tl;dr but congrats for still remembering your math classes. This didn't involve anything from math classes, this was algorithms. You can go on pretending that it's a domain-specific problem, but it's not. Also, it's not a task, it's an interview question. Interviews are not about simulating work and pretending to be all professional. They are about seeing whether or not you suck at programming, especially the first phone screen.
|
|
#
?
Mar 18, 2012 23:51
|
|
|
Call it whatever you like, it's still a wanky bullshit interview question and if you judge your candidates on whether they can answer that on the phone, then good luck to you.
|
|
#
?
Mar 18, 2012 23:54
|
|
|
Shrughes, what is your educational background? I never got any of this from my data structures class and I'm not seeing it so far in algorithms, though we haven't gotten to divide and conquer yet. I feel like the only subject I've studied that would have helped me to solve that problem was abstract algebra.
|
|
#
?
Mar 19, 2012 00:11
|
|
|
Safe and Secure! posted:Shrughes, what is your educational background? I never got any of this from my data structures class and I'm not seeing it so far in algorithms, though we haven't gotten to divide and conquer yet. Math, CS, and some experience with functional programming.
|
|
#
?
Mar 19, 2012 00:27
|
|
|
No matter how much you want to pretend this is a general programming question, it relies on the application of specific facts about mathematics and low level optimizations that are highly inapplicable to 99% of problems developers face.
|
|
#
?
Mar 19, 2012 00:31
|
|
|
baquerd posted:No matter how much you want to pretend this is a general programming question, it relies on the application of specific facts about mathematics and low level optimizations that are highly inapplicable to 99% of problems developers face. WTF??? There are no low level optimizations here. Are you just making stuff up? You're like that guy who wanted to make an MMO. A function being associative is not a math-specific thing. That's a commonly exploited fact in algorithm design. And if you can't exploit these mathematical properties (e.g. of string concatenation being associative) you're a bad person.
|
|
#
?
Mar 19, 2012 00:34
|
|
|
shrughes posted:WTF??? There are no low level optimizations here. Are you just making stuff up? You're like that guy who wanted to make an MMO. I'll agree with you that if you want a specialist in mathematical algorithms, they should know how to do this or be able to figure it out in short order. Outside of Project Euler though I just don't run into this sort of stuff. Optimizations I have run into professionally have far more to do with architectural concerns or general data structure choices than algorithms at an operator level.
|
|
#
?
Mar 19, 2012 00:41
|
|
|
shrughes posted:Any good developer would recognize that you can....
|
|
#
?
Mar 19, 2012 01:01
|
|
|
baquerd posted:I'll agree with you that if you want a specialist in mathematical algorithms, they should know how to do this or be able to figure it out in short order. Outside of Project Euler though I just don't run into this sort of stuff. Optimizations I have run into professionally have far more to do with architectural concerns or general data structure choices than algorithms at an operator level. I do. I don't work on "mathematical algorithms" either. The point is that this problem solving is not specific to exponentiation. This is general algorithm problem solving skills, and taking advantage of properties of functions like associativity is one of the classical tricks. In the recent past I've exploited the fact that max(x,y) is associative and commutative in designing a data structure (storing max(a property of elements of subtree) values on subtree nodes), and similarly with the fact that addition is associative, and I've done careful algebra to prove the correctness of the layout of a b-tree leaf node, and, uh, exploited the fact that x_i - (y + d) = (x_i - d) - y in another data structure (allowing you to change y by d instead of changing every x_i by d, the point of this was to let us reuse an existing data structure we had for something). At my previous job, which would look more like a typical corporate software development job, we also had to deal with the math of assigning scores to customer relationships and ensuring that our search engine produced stable results and met other criteria, we had customers complaining to us about the ordering of results and satisfying all possible complaints would be impossible due to Arrow's impossibility theorem. And there we also had a datastructure for concatenating strings efficiently. (Web development, after all, is all about the art of concatenating strings.) It was just a tree of strings, and once it was constructed, it dumped the output into a StringBuilder, which works because string concatenation is associative! Oh I'm sorry, my bad, web development is just too mathematical. I guess web developers who can't exploit associativity had better find something new to work on. Maybe they could make a database that eschews relational algebra and does everything behind a global write lock.
|
|
#
?
Mar 19, 2012 01:13
|
|
|
baquerd posted:Optimizations I have run into professionally have far more to do with architectural concerns or general data structure choices than algorithms at an operator level.
|
|
#
?
Mar 19, 2012 01:14
|
|
|
shrughes posted:I do. I don't work on "mathematical algorithms" either. The point is that this problem solving is not specific to exponentiation. This is general algorithm problem solving skills, and taking advantage of properties of functions like associativity is one of the classical tricks. I take your point, and that's certainly impressive. You are excellent at algorithms and data structures, and probably a good developer. That said, I really don't run into these sorts of problems often, and when I do profiling rarely shows this sort of algorithmic efficiency to be the problem. I have in fact many times wasted effort in creative optimizations that ultimately did not help performance from a user perspective despite being many times more efficient than the initial implementation. When you worked out the equivalency problem to reuse that data structure, did you first try a naive solution of copying the data to fit the specific problem domain and then profile the code to determine there was a problem? Can you be certain that your work was fruitful or was it a digression into academic masturbation? Does knowing the exact efficiency of a StringBuilder matter, or is it knowing that it is the most efficient way of constructing large strings from constituent strings enough?
|
|
#
?
Mar 19, 2012 01:29
|
|
|
baquerd posted:Can you be certain that your work was fruitful or was it a digression into academic masturbation? Definitely certain that work was not academic masturbation, we didn't need to profile it, it was a matter of writing 2 blocks to disk in almost all cases versus writing 1 + N blocks to disk where N is easily a hundred or a thousand. This was actually the quick and ugly solution. 2 is really way too much, but it would only actually cost 2 blocks per operation in certain modes, and that's for a certain kind of operation (deleting stuff). Eventually we got it down to "practically zero" by rewriting another data structure instead of using this auxiliary data structure. quote:Does knowing the exact efficiency of a StringBuilder matter, or is it knowing that it is the most efficient way of constructing large strings from constituent strings enough? Knowing it's the most efficient way would suffice, but that's not the point here. My point there was that the algorithm exploits the fact that ((x + y) + z) + (w + (v + t)) = (((((("" + x) + y) + z) + w) + v) + t). This isn't exactly a hard thing to see, and it's the sort of situation where people are comfortable taking advantage of the fact that an operation is associative, rather than regarding this as some kind of alien mathematical algorithm. To avoid making this datastructure we'd have had to make a more significant refactoring to our code. (Passing a StringBuilder through to every function that returned one of these instead of having them return a string would have been more efficient, but that would just be an intolerable cruelty.) Edit: Also I've found that almost every person I've interviewed has had no problem adding a bit of summary information to a tree-like data structure that can be computed efficiently because it's built from an associative operation: in particular, storing on each node in a tree the number of elements in the subtree. You compute that incrementally by adding together the values stored on the children whenever you make a change to the node, and it works because addition is associative. They had to come up with that to solve some kind of problem, like finding the n'th element from the left, or uniformly randomly selecting a value from the data structure. shrughes fucked around with this message at 01:52 on Mar 19, 2012 |
|
#
?
Mar 19, 2012 01:47
|
|
|
pigdog posted:Call it whatever you like, it's still a wanky bullshit interview question and if you judge your candidates on whether they can answer that on the phone, then good luck to you. For the other part of the question, spotting that a decimal number mod 10^n is the last n digits of that number is not an unreasonable expectation for a computer scientist. The only vaguely number theoretical part of the whole exercise is knowing that you can perform the modulo operation after each step of the above exponentiation algorithm, since (a mod n) * (b mod n) = (a * b) mod n. Knowing the basic properties of modular arithmetic is also not an unreasonable expectation for a computer scientist. In fact, knowing the modular exponentiation algorithm (or at least knowing that there is an efficient modular exponentiation algorithm) is not that unreasonable. For what it's worth, I have no formal background in mathematics above the mandatory first year stuff, and I got that question instantly.
|
|
#
?
Mar 19, 2012 01:49
|
|
|
|
| # ? Apr 29, 2024 01:00 |
|
|
shrughes posted:Definitely certain that work was not academic masturbation, we didn't need to profile it, it was a matter of writing 2 blocks to disk in almost all cases versus writing 1 + N blocks to disk where N is easily a hundred or a thousand. This was actually the quick and ugly solution. 2 is really way too much, but it would only actually cost 2 blocks per operation in certain modes, and that's for a certain kind of operation (deleting stuff). Eventually we got it down to "practically zero" by rewriting another data structure instead of using this auxiliary data structure. Disk operations are certainly expensive, and creative data structure usage to limit writes is a useful pursuit. I tend to disagree that this sort of knowledge application comes up often enough that knowing it intuitively as a relative issue during a phone interview is essential, though I cannot disagree it is a good thing to know. quote:Knowing it's the most efficient way would suffice, but that's not the point here. My point there was that the algorithm exploits the fact that ((x + y) + z) + (w + (v + t)) = (((((("" + x) + y) + z) + w) + v) + t). This isn't exactly a hard thing to see, and it's the sort of situation where people are comfortable taking advantage of the fact that an operation is associative, rather than regarding this as some kind of alien mathematical algorithm. I think the disconnect that many people, including myself, are having is the merging of associative operations with number theory. Though I actually have an (undergrad from 10 years ago) degree in mathematics, the number theory needed to intuitively see the problem domain as an associative grouping problem just isn't in my worldview. If the interviewer were willing to provide pertinent hints about number theory that would logically follow to this problem domain, I would be much more receptive to using this as an interview question. I do feel you on the excessive passing around of object references being a cruelty. I can't count the number of times a code adjustment like that is desirable from an efficiency or organization standpoint while being extremely aggravating from an implementation and code "beauty" standpoint. I will be the first to admit I could benefit from more knowledge of the theory of data structures and algorithms.
|
|
#
?
Mar 19, 2012 01:59
|
|