Skip to content

Instantly share code, notes, and snippets.

@yangtaeho

yangtaeho/2_1_egypt_product.js

Last active April 28, 2022 15:03
Show Gist options
  • Save yangtaeho/a315b990a2ef931ea24f163305109c64 to your computer and use it in GitHub Desktop.
Save yangtaeho/a315b990a2ef931ea24f163305109c64 to your computer and use it in GitHub Desktop.
Download ZIP
study_algorithm_ramble_c2_220428
Raw
2_1_egypt_product.js
const odd = n=> !!(n & 0x1);
const half = n=>n >> 1;
{
// ๋‚ด๊ฐ€ ์ง ๊ฑฐ
const odd = n=>half(n) == half(n - 1);
const half = n=>Math.floor(n/2);
}
{
// hika pp. 29
// n == parseInt(n/2) + parseInt(n/2); // ์ง์ˆ˜์ธ๊ฐ€? #1
// n == parseInt(n/2) *2; // ์ง์ˆ˜์ธ๊ฐ€? #2
const even =n=>parseInt(n/2)*2;
const odd =n=>even(n-1);
const half =n=>parseInt(n/2);
// 4/2 = 2
// 5/2 = 2
// odd half + n
// hika 2์˜ ์ฒด์ธ์ด ์•„๋‹ˆ๋ผ 3์˜ ์ฒด์ธ์œผ๋กœ ๋งŒ๋“ ๋‹ค๋ฉด..
// pp.30 ~
/*
int mul(int n, int a){
if(n==1) return a
int result = mul1(div3(n), a+a+a)
if(n%2 == 2) r = r+ a+ a
else if(n%2 == 1) r = r + a
return r
}
*/
const div3 = n=>!!parseInt(n/3)*3;
const odd3 = n=>n == n/3 + n/3 + n/3;
const div4 = n=>!!parseInt(n/4)*4;
const test = (n)=> {
console.log(n, div3(n) + n);
console.log(n, div3(n) + n + n);
console.log(n, odd3(n) + n + n);
console.log(n, div4(n));
};
test(15);
test(6);
test(16);
}
{
const div2 = n=>!!parseInt(n/2)*2;
const odd = n=>div2(n) + 1;
const test = (n)=> {
console.log(n, div2(n));
console.log(n, odd(n));
};
test(15);
test(6);
test(16);
}
/*
{
div2 - 1
div3, div3 -1 ,div3 -2
div4, div4 - 1, -2, -3
const half = n => parseInt(n/2);
4
100
5
101
5/2 == 2, 1
}
{
์‚ฌ์‹ค ๋‚˜๋ˆ—์…ˆ์€ ๋น„์‹ผ ์—ฐ์‚ฐ์ด๊ธฐ ๋•Œ๋ฌธ์— + ๋ฅผ odd, half ๋กœ ๋Œ€์ฒดํ•œ ๊ฒƒ์€
์˜คํžˆ๋ ค ์†ํ•ด์ธ ์…ˆ..
}
*/
class C2 {
multiply0 (n, a){
if (n < 1) return 0;
if (n == 1) return a;
return this.multiply0(n - 1, a) + a;
}
multiply1 (n, a){
if (n < 1) return 0;
if (n == 1) return a;
let result = this.multiply1(half(n), a + a);
if (odd(n)) {
result += a;
}
return result;
}
multiply_by_15 (a){
let b = (a + a) + a;
let c = b + b;
return (c + c) + b;
}
mult_acc0(r, n, a) {
if (n < 1) return r;
if (n == 1) return r + a;
if (odd(n)) {
return this.mult_acc0(r + a, half(n), a + a);
} else {
return this.mult_acc0(r, half(n), a + a);
}
}
mult_acc1(r, n, a) {
if (n < 1) return r;
if (n == 1) return r + a;
if (odd(n)) {
r = r + a;
}
return this.mult_acc1(r, half(n), a + a);
}
/**
* ์ฝ”๋“œ๋กœ๋Š” mult_acc1 ์ด ๋” ํšจ์œจ์ .
* n ==1 ์„ ๋จผ์ € ํ•˜๋Š” ๊ฒŒ ๋งž๋‹ค
*/
mult_acc2(r, n, a) {
if (n < 1) return r;
if (odd(n)) {
r = r + a;
if (n == 1) return r;
}
return this.mult_acc2(r, half(n), a + a);
}
/**
* ๊ผฌ๋ฆฌ ๋ฌผ๊ธฐ ์ตœ์ ํ™”
*/
mult_acc3(r, n, a) {
if (n < 1) return r;
if (odd(n)) {
r = r + a;
if (n == 1) return r;
}
n = half(n);
a = a + a;
return this.mult_acc3(r, n, a);
}
/**
* ์žฌ๊ท€๋ฅผ ๋ฃจํ”„๋กœ
*/
mult_acc4(r, n, a) {
if (n < 1) return r;
while(true) {
if (odd(n)) {
r = r + a;
if (n == 1) return r;
}
n = half(n);
a = a + a;
}
console.log('๋ฃจํ”„ ๋ฐ–์œผ๋กœ.. ๋‚˜์˜ค์ง€ ์•Š์Œ', r, n, a);
return r;
}
multiply2 (n, a){
if (n < 1) return 0;
if (n == 1) return a;
return this.mult_acc4(a, n - 1, a);
}
/**
* while ๊นŒ์ง€ ์“ธ ํ•„์š” ์žˆ๋‚˜?
*/
multiply3 (n, a){
if (n < 1) return 0;
while(!(odd(n))) {
a = a + a;
n = half(n);
}
if (n == 1) return a;
return this.mult_acc4(a, n - 1, a);
}
/**
* trash.. ์„ฑ๊ธ‰ํ•œ ์ตœ์ ํ™”...
*/
multiply4 (n, a){
if (n < 1) return 0;
while(!(odd(n))) {
a = a + a;
n = half(n);
}
if (n == 1) return a;
// even(n-1) -> n -1 != 1
return this.mult_acc4(a, half(n - 1), a + a);
}
}
Raw
index.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>chapter2</title>
<script src="2_1_egypt_product.js"></script>
<script>
const init = ()=> {
[...Array(9)].map((v,i) => {
console.log('i:', i, ', odd', odd(i), ', half', half(i));
});
const test =(fname, a, b)=> {
const c2 = new C2();
console.log(fname.padStart(14, ' '), a, b, c2[fname](a, b));
};
const test2 =(fname, r, a, b)=> {
const c2 = new C2();
console.log(fname.padStart(14, ' '), a, b, c2[fname](r, a, b), r);
};
[...Array(10)].map((v,i) => {
[...Array(10)].map((v,j) => {
console.log('i:', i, ', j', j, i*j);
});
});
[...Array(10)].map((v,i) => {
[...Array(10)].map((v,j) => {
console.log('i:', i, ', j', j, i*j);
test('multiply0', i, j);
test('multiply1', i, j);
test2('mult_acc0', 0, i, j);
test2('mult_acc1', 0, i, j);
test2('mult_acc2', 0, i, j);
test2('mult_acc3', 0, i, j);
test('multiply2', i, j);
test('multiply3', i, j);
test('multiply4', i, j);
});
test('multiply_by_15', i);
});
[49371].map((v,i) => {
[289].map((ve,j) => {
test('multiply2', v, ve);
});
});
};
</script>
</head>
<body onload="init()">
<button type="button" onclick="init()">์‹œ์ž‘</button>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment