Created
April 7, 2020 03:30
-
-
Save tylerlmz1/c9a96354b992e056aa84d8d32eb37b33 to your computer and use it in GitHub Desktop.
Russian peasant algorithm written in Node.js
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const assert = require('assert').strict | |
function russianPeasantAlgo(a, b) { | |
aArray = [] | |
bArray = [] | |
// process first number | |
while (a > 0.99) { | |
aArray.push(a) | |
a = Math.trunc(a / 2) | |
} | |
// process second number | |
while (bArray.length != aArray.length) { | |
bArray.push(b) | |
b = b * 2 | |
} | |
// make sure both arrays are of the same length | |
assert.strictEqual(aArray.length, bArray.length) | |
// remove elements in bArray that aArray's corresponding index is even number | |
removeTheseIndexes = [] | |
aArray.forEach(num => { | |
if (num % 2 == 0) { | |
const evenNumIndex = aArray.indexOf(num) | |
removeTheseIndexes.push(evenNumIndex) | |
} | |
}) | |
for (var i = removeTheseIndexes.length - 1; i >= 0; i--) { | |
bArray.splice(removeTheseIndexes[i], 1) | |
} | |
// sum numbers in bArray | |
const arrSum = arr => arr.reduce((a, b) => a + b, 0) | |
const RPanswer = arrSum(bArray) | |
return RPanswer | |
} | |
// randomly generate integers and check the algo's results | |
// against multiplication | |
const max = 99999999 | |
for (let i = 0; i < 50; i++) { | |
const a = Math.floor(Math.random() * Math.floor(max)) | |
const b = Math.floor(Math.random() * Math.floor(max)) | |
assert.strictEqual(a * b, russianPeasantAlgo(a, b)) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment