多倍長演算-掛け算-

 掛け算のプログラムを書いた。

基数は4にとってみた。

多分基本的にはこういう感じなんだろう。

コマンドラインの二つの引数(10進数)を掛け算し、結果を4進数で表示する。

4進数を10進数表示にすることもしたかったがまだ出来ていない。



安直にコマンドライン引数をatoiで変換しているため、受け取れる最大値は

2^31-1=2147483647

である。これに3をかけるため、google先生によると6442450941となるはずである。

4進数では11333333333333331である。きちんと計算できている。

何も考えずにint型で結果を受け取ろうとするとオーバーフローする領域の

掛け算が可能となった。しかも、精度を上げることは簡単である。

単に配列のサイズをどんどん大きくしていくだけだから。

wikipediaで任意精度演算の項目に、「桁の精度がシステムの利用可能なメモリ容量

にのみ制限される計算技法」と書かれているのはこのことだ。

ただ、今回のような愚直なアルゴリズムだと4進数でN桁同士の掛け算の計算量は

O(N^2)となる。計算量の少ないアルゴリズムは色々存在しているらしい。

あと気になるのは小数を二進数でどう扱うかだ。勉強します。

続きを読む >>
ジャジャガッチ | コンピュータ | 21:19 | comments(0) | trackbacks(0) |

大きい数を用意する

 unsigned int(符号なし4byte整数)で考える。

unsigned int a;

と宣言するとaは0〜2^32-1までの数しか扱えない。

しかし、例えばa[64]という2bit配列を用意すると0〜2^64-1までの数が扱える。

これは二進数を使った例だが、四進数を使うとすると2bit配列a[]を用意し、

各要素に0〜3を入れればよい。もっと言えば2^32進数を使うことにして

unsigned int a[]を用意し、各要素に0〜2^32-1を格納してもよい。

あとは演算をどう行うか。
ジャジャガッチ | コンピュータ | 15:09 | comments(0) | trackbacks(0) |

符号付二進数

  多倍長演算について勉強するには色々基礎知識がいる。

まず、符号付二進数について勉強した。

2bitで考えよう。

符号なしでは0b00(0),0b01(1),0b10(2),0b11(3)の4つの数がある。

単なる記号だから適当に0,1,-1,2という風に割り当てるのもひとつの手ではあるが、計算を行おうと思うと不便である。

我々がよく知っている計算ルールで足してゼロになる数を逆元と定義するのがよい。

0b01に足して0になるのは0b11である。結果は0b100になるが3bit目は無視する。

0b10に対しては0b10を足せば0になるため、負の数は定義できない。よって2bit符号付二進数

では

0b00(0),0b01(1),0b10(2),0b11(-1)となる。

元の二進数に足して0になる数を補数という。補数は、全ビットを反転して1足せば求まる。

確認プログラムを書いた。

#include <stdio.h>

int main(void)
{
    int a = 1;
    unsigned int b =1;
   
    printf("%d¥n",~a);
    printf("%u¥n",~b);
   
    return 0;
}

~はnot演算を意味する。intは4byteなので1は

a = 0b00000000000000000000000000000001

~a = 0b11111111111111111111111111111110

これは0b10(=2)の補数なので-2であり、符号なしでは2^32-1-1=4294967294

である。実行結果は確かにその通りになる。
ジャジャガッチ | コンピュータ | 14:39 | comments(0) | trackbacks(0) |

多倍長演算

 OPENMPを少し勉強したので、円周率でも計算してみるか、と思ったのだが、

さっそくつまづいた。

愚直にdoubleとかで変数を用意して円周率を計算してみても精度は小数点以下

数桁しかない。doubleは8byte分の情報しか格納できないためだ。

精度よく計算するためには多倍長演算というものをしなくてはならない。
ジャジャガッチ | コンピュータ | 14:34 | comments(0) | trackbacks(0) |

OPENMP

 最近のCPUはマルチコアが常識になっている。

普通にプログラムを書くだけだとマルチコアの恩恵が受けられない。

現在のコンパイラはまだ自動的に全てのコアに計算を割り振ることまではしてくれないらしい。

そこで自分で明示的に計算を割り振る必要がある。

そのひとつの方法がOPENMP。

VC++ expressでも使えるが
「windows sdk for windows server 2008 and .net framework 3.5」

をインストールしておく必要がある。

プロジェクト=>プロパティ=>C/C++=>言語

のところでOPENMPを有効にしておけばこコンパイルが通る。

DebugモードじゃなくてReleaseモードにしておかないとエラーが出るみたい。

ちなみにコマンドラインでは

cl hoge.c /openmp

とすることでコンパイルできる。初めてのOPENMPプログラム。

#include <stdio.h>
#include <omp.h>

int main()
{
    #pragma omp parallel
    printf("Hello,OPENMP!¥n");
       
    return 0;
}

僕の環境は4コアなので"Hello,OPENMP"が4回表示される。
ジャジャガッチ | コンピュータ | 12:01 | comments(0) | trackbacks(0) |

KINECTセンサープログラミング

 昨日本屋へ行ったら「KINECTセンサープログラミング」という本が売っていた。

一ヶ月くらい前に出た本らしい。

僕がKINECTで遊び始めた頃にはこういう参考書はなかったように思う。

とりあえず購入。

中途半端なところで止まっていたのでまたKINECTで遊ぶことにする。

今日は射影についてちょいと勉強。

前やったときはこの辺を適当にやったので結果がもうひとつだった。

もう少しまじめにやろうかな、ということで。
ジャジャガッチ | コンピュータ | 22:13 | comments(0) | trackbacks(0) |

角度

 最近角度というものについて考える機会があった。

何故数学ではdegreeではなくradを用いるのか。

radは数学上極めて自然な単位だ。

単位円の円弧の長さで角度を定義しようというのだから。

ではdegreeはどうだろうか。

そもそも何故一周を360度と定義するのか。

wikipediaによると一年の日数に由来するらしい。

つまり、数学的には何の必然性もない。

どこか遠い星の宇宙人たちもradという単位は使っているに違いないが、

degreeという単位は使っていないだろう。
ジャジャガッチ | 数学 | 22:07 | comments(0) | trackbacks(0) |
1/1PAGES | |

07
--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
--
>>
<<
--
PR
RECOMMEND
RECENT COMMENT
MOBILE
qrcode
OTHERS
Since 2013/09/17
LATEST ENTRY
CATEGORY
ARCHIVE
LINKS
PROFILE
SEARCH