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