Egyptian Multiplication Solution

Contributors
1

What is your hint or solution suggestion?

function eth_mult(a, b) {
var aL = [a], bL = [b], tot =0;

while(a>1) { 
 a = Math.floor(a/2); 
 aL.push(a);
 b *=2; 
 bL.push(b);
}
for(var i=0; i< bL.length-1; i++) {
    bL[i] = (aL[i]%2==0) ? 0: bL[i];
    aL[i] = (aL[i]%2 == 0)? 0: aL[i];
    tot+= bL[i]; 
} 
return tot; 
}

Challenge: Ethiopian multiplication

Link to the challenge:

2

Your loop doesn’t go far enough. It stops one short of the end.

3

Right idea, wrong implementation sort of thing? Tried both separate cases where ( <bL.length) and tot += bL[bL.length -1] after … This is the version that passed m8…

4

I agree that running to length-1 looks fishy

What about

function eth_mult(a, b) {
  // required functions
  const halve = (n) => Math.floor(n/2);
  const double = (n) => n + n;
  const isEven = (n) => n % 2 === 0;

  // setup variables
  let [left, right] = [a, b].sort((a, b) => a - b);
  let total = isEven(left) ? 0 : right;

  // Egyptian algorithm
  while (left > 1) {
    left = halve(left);
    right = double(right);
    if (!isEven(left))
      total += right;
  }

  // return result
  return total;
}

Not sure if it runs, but it should be a little simpler logic

Recursive version

const halve = (n) => Math.floor(n/2);
const double = (n) => n + n;
const isEven = (n) => n % 2 === 0;

function eth_mult(a, b) {
  return a > 1 ? (eth_mult(halve(a), double(b)) + (isEven(a) ? 0 : b)) : b;
}
5

The solution is that?

Sorry, I am confused…

6

I agree that the complexity would be reduced slightly… I’ll debug it and see if it runs. If it does pass all states,I’ll let you know. Otherwise, posting the debugged, complete code on similar basis. Regardless if such works, I agree that it wasn’t the most efficient method I was using. Always room to improve the method, but since it didn’t exceed O(n+k) I didn’t really care to improve it… I get that it’s WCS complexity shouldn’t exceed O(1) but still

7

I’m still not sure why the -1 is working. That one has me scratching my head. We have basically the same logic, with mine slightly streamlined.

8

It should be working, last I checked, but it’s just people complaining about complexity… Honestly sounds like an Among Us Forum…

9

The code didn’t pass with -1 and did pass without it for me. 🤷

10

Yeah, I dunno dude… It’s kinda just ‘whatever gets the debugger’s motor revving’, or something…

11

In any case, since this challenge has no solutions, I’d be happy to add one or both of ours.

Mine would need a brief explanation.

For yours, I’d ask for a brief explanation, the -1 issue sorted out, a bit clearer variable names, and triming a bit of extra calculation in your for loop.

12

aList, bList, and total… I’m just curtailing for brevity.

13

Yeah, I come from C/Fortran background so I appreciate the desire for brevity. But after spending time in languages with more verbose conventions, such as Julia and Rust, I’ve grown fond of using full words when able. Personal preference, I suppose.

The cool thing with JS is that production code often gets ‘uggified’ and the variable names collapsed to short incomprehensible names to save space, so we’re free to use as big of names as we like for readability and it won’t effect end code size.

1 Like
14

The description makes it sound like you are supposed to create 3 function for each functionality (half/double/check if even). I also think using multiplication in the code kind of defeats the purpose of doing multiplication without using multiplication.

Here is the actual rosettacode with the JS solutions

Anyway, just for reference here is the version they have just slightly rewritten.

function eth_mult(m, n) {
  const halve = (n) => Math.floor(n / 2);
  const double = (n) => n + n;
  const isEven = (n) => n % 2 === 0;

  let sum = 0;
  const left = [m];
  const right = [n];

  while (left[0] !== 1) {
    left.unshift(halve(left[0]));
    right.unshift(double(right[0]));
  }

  for (var i = left.length - 1; i > 0; i -= 1) {
    if (!isEven(left[i])) {
      sum += right[i];
    }
  }
  return sum + right[0];
}

console.log(eth_mult(17, 34)); // 578
15

Yeah, I thought about making my version use those functions, but I was coding on my phone and feeling lazy. That’s such a bizarre requirement since those functions are so basic and only needed in one place in the code.

Edit: I’ve updated my solution to reflect this strange requirement.

I’m still not wild about making a data structure to hold the left and right values instead of just adding as you go. Less efficient that way.

16

It does seem a bit strange, at least unless you can come up with a version that is more composable. Like something recursive.

Here is a recursive version, I just took the code from the AutoHotkey code solution.

const halve = (n) => Math.floor(n / 2);
const double = (n) => n + n;
const isEven = (n) => n % 2 === 0;

const eth_mult = (a, b, r = 0) => {
  return a == 1 ? r + b : eth_mult(halve(a), double(b), !isEven(a) ? r + b : r);
};

console.log(eth_mult(17, 34)); // 578
17

Oh, I like the recursive approach. Its a shame more browsers don’t optimize tail call recursion.

19

Thank you for your guide post contribution. I have taken your suggestions and included them in the guide post.

We look forward to your further contribution.

1 Like