ほんまの走り書き技術メモ

C言語でKaratsuba開平を利用して整数の平方根と余りを求める

c, programing, アルゴリズム | 18:25 |

math.hのsqrt(f)を使わずに整数の平方根を求めてみた。(intが4byteであるマシンでのみ動作)

sqrtmod0はアルゴリズム上0x40000000以上の値の平方根を計算でようなので、0x40000000以上の値はKaratsuba開平を利用して求めている。

↓は乱数で平方根と余りを求めてsqrtで求めたものとassertをし続けるプログラムです。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

#define BASE (sizeof (unsigned int) * 8 / 4)

int sqrtmod(unsigned int n, unsigned int *pmod);
int sqrtmod_karatsuba(unsigned int n, unsigned int *pmod);
int sqrtmod0(unsigned int n, unsigned int *pmod);

int sqrtmod(unsigned int n, unsigned int *pmod) {
	return sqrtmod_karatsuba(n, pmod);
}

int sqrtmod_karatsuba(unsigned int n, unsigned int *pmod) {
	int s, s1, s0, r, r1, r0;

	if ((0xc0000000 & n) == 0) {
		return sqrtmod0(n, pmod);
	}

	s1 = sqrtmod0(n >> (BASE * 2), &r1);

	r0 = (r1 << BASE) | ((n >> BASE) & 0x000000ff);
	s0 = r0 / (s1 << 1);
	r0 -= s0 * (s1 << 1);

	s = (s1 << BASE) + s0;
	r = ((r0 << BASE) | (n & 0x000000ff)) - s0 * s0;
	if (r < 0) {
		r += (s << 1) - 1;
		s--;
	}
	if (pmod) *pmod = r;
	assert(s * s + r == n);

	return s;
}

int sqrtmod0(unsigned int n, unsigned int *pmod) {
	int p = 0, q = 1, r = n, h = 0;

	while (q <= n) {
		q = q << 2;
	}

	while (1 != q) {
		q = q >> 2;
		h = p + q;
		p = p >> 1;
		if (r >= h) {
			p = p + q;
			r = r - h;
		}
	}
	if (pmod) *pmod = r;
	assert(p * p + r == n);

	return p;
}

int main(int argc, char **argv) {
	unsigned int n, s1, r1, s2, r2;

	srand((unsigned)time(NULL));
	while (1) {
		n = rand();
		s1 = sqrtmod(n, &r1);
		s2 = sqrt(n);
		r2 = n - s2 * s2;
		assert(s1 == s2 && r1 == r2);
	}

	return 0;
}

とりあえずassertエラーが出ないので、実装は出来ているらしい。。

参考：

2 Karatsuba系列のアルゴリズム

Square Root Algorithm - GNU MP 5.0.5

ツイートする

Rubyでn桁の円周率を求める

Ruby, アルゴリズム | 18:42 |

検証用に使っていた物です。

len = ARGV[0].to_i
B = 10 ** len
B2 = B << 1
pi = (len * 8 + 1).step(3, -2).inject(B) {|a, i| (i >> 1) * (a + B2) / i} - B
puts "3.#{pi}"

# time ruby pi.rb 100
3.141592653589793238462643383279502884197169399375105820974944592307816406286208
9986280348253421170679

real    0m0.045s
user    0m0.027s
sys     0m0.007s

10万桁位なら2分前後で行けるはずです。

※ウチのPCはショボイのでもっと早いかも

ツイートする

ASCIIコード表見て今頃気づいたこと

programing, c, memo | 09:15 |

toupperとtolowerって、cが英字であることが担保されていればこれでいい

#define TOUPPER(c) ((c) & ~0x20)
#define TOLOWER(c) ((c) |  0x20)

ツイートする

Linuxでユーザ管理関係のコマンドまとめ

sh, linex | 23:30 |

ユーザ確認

各ユーザには大体/home下に自分専用のディレクトリがあるので、

ls -l /home

で確認できる。

ユーザ追加

useradd ユーザ名

グループ、パスワードも一気に

useradd -g グループ名 -p パスワード ユーザ名

ユーザに利用有効期限を付ける

useradd -e yyyy-mm-dd ユーザ名

ログインシェルをnologinにして、TelnetやSSHでログインさせないようなユーザを作る

メールとHPは許可

useradd -s /sbin/nologin ユーザ名

同様に、メールしか利用できないようなユーザを作る

useradd -s /sbin/false ユーザ名

発効から指定日数までにログインしないと、無効になるユーザを作る

useradd -f 日数 ユーザ名

ユーザ削除

userdel ユーザ名

ユーザのホームディレクトリも消す場合は、

userdel -r ユーザ名

パスワード変更

自分のパスワードなら

passwd
の後、パスワード入力。

管理者が他のユーザのパスワードを変更する場合は、

passwd ユーザ名

グループを追加

groupadd グループ名

グループは、

cat /etc/group

で確認できる。

グループ名変更

groupmod -l 旧グループ名 新グループ名

グループを削除

groupdel グループ名

ツイートする

パスワードファイル操作のまとめ

sh, linex | 23:30 |

パスワードファイル新規作成

htpasswd -c ファイル名 ユーザ名
New password: パスワード
Re-type new password: パスワード

ファファイルに追加（パスワード変更）

htpasswd ファイル名 ユーザ名
New password: パスワード
Re-type new password: パスワード

コマンド引数でパスワードを指定

htpasswd -cb ファイル名 ユーザ名 パスワード

ユーザ削除

htpasswd -D ファイル名 ユーザ名

ツイートする