Yuki Nakata's Blog

天才 中ちゃん♪

素数判定プログラム2 C言語GMPライブラリ の続きです。

GMPライブラリを使って素数判定プログラムを書いていきます。

gmpには素数を判定する関数が用意されています。

int mpz_probab_prime_p(mpz_t n, int reps);

戻り値で素数かどうかを判定します。

2が帰ってきたときは絶対素数 (definitely prime)
1のときは素数っぽい、(probably prime)
0のときは合成数つまり素数ではない、です。

repsはミラーラビン法のパラメータですが、通常25を指定しておけばいいそうです。

実行してみてください。一瞬で計算が終わりますよ。

$ gcc prime4.c -o prime4 -lgmp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <gmp.h>

int main(void)
{
mpz_t number;
int answer = 0;

  mpz_init(number);

mpz_set_str(number, "940461086986004843694934910131104208392131088686023657900173332902199657733778583489", 10);
 
answer =  mpz_probab_prime_p(number, 25); 

mpz_out_str(stdout, 10, number);
if (answer) {
printf(" は素数だよ\n");
} else {
printf(" は素数じゃないよ\n");
}
return 0;
}

素数判定プログラム C言語の続きです。

今度はGMPライブラリを使って素数判定プログラムを書いていきます。

GMPプログラミング初めてです。

ぶっつけ本番でも大丈夫でしょう。

変数をそれぞれ保存しないといけないのでプログラムが汚くなってしまいました。

C言語風のコメントも書いておきました。見づらくなったかも。w

GMPライブラリーもマスター出来ました。

//$ gcc prime3.c -o prime3 -lgmp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <gmp.h>

int isPrime(mpz_t number)
{
mpz_t i, four, twomod, threemod, sqrt, tmpmod, tmpmod2, iplus2;

mpz_init(i);
mpz_set_str(i, "5", 10); //10進数 5で初期化 i = 5;

mpz_init(sqrt);
mpz_sqrt(sqrt, number); 

mpz_init(four);
mpz_set_str(four, "4", 10);//10進数 4で初期化 four = 4;
mpz_init(twomod);
mpz_set_str(twomod, "0", 10);//10進数 0で初期化 twomod = 0;

mpz_init(threemod);
mpz_set_str(threemod, "0", 10);//10進数 0で初期化 threemod = 0;

mpz_init(tmpmod);
mpz_init(tmpmod2);
mpz_init(iplus2);

mpz_mod_ui(twomod, number, 2); //twomod = number % 2;
mpz_mod_ui(threemod, number, 3); //threemod = number % 3;

if (mpz_cmp_ui(number, 1) > 0 && 0 < mpz_cmp(four, number)) {
return 1;
} else if (mpz_get_ui(twomod) == 0 || mpz_get_ui(threemod) == 0) {
return 0;
} else {
for (i; 0 <= mpz_cmp(sqrt, i); mpz_add_ui(i, i, 6)) {
mpz_mod(tmpmod, number, i); //tmpmod = number % i;
mpz_add_ui(iplus2, i, 2); //iplus2 = i + 2;
mpz_mod(tmpmod2, number, iplus2); //tmpmod2 = number % iplus2;
if (mpz_get_ui(tmpmod) == 0 || mpz_get_ui(tmpmod2) == 0) {
return 0;
}
}
}

mpz_clear(i);
mpz_clear(sqrt);
mpz_clear(four);
mpz_clear(twomod);
mpz_clear(threemod);
mpz_clear(tmpmod);
mpz_clear(tmpmod2);
mpz_clear(iplus2);
return 1;
}

int main(void)
{
mpz_t number;
int answer = 0;

  mpz_init(number);

mpz_set_str(number, "150094772735952593", 10);

answer = isPrime(number);

mpz_out_str(stdout, 10, number);
if (answer) {
printf(" は素数だよ\n");
} else {
printf(" は素数じゃないよ\n");
}
mpz_clear(number);
return 0;
}

150094772735952593 は18桁の素数です。

ここに判定する数字を入力してください。
 
素数サンプル 楽勝レベル
31389448217
282437925089
1853028778786433
5559077746424707
150094772735952593

PCだと厳しい 一気に時間がかかります。終わらないかもね。
8862938260389989451257
26588814640432479998443

実はGMPライブラリには素数を判定する関数が用意されています。

それを呼べば一発で素数かどうかを判定することができます。

次回に続きます。 素数判定プログラム3 C言語GMPライブラリ

参考サイト
多倍長整数演算ライブラリ (GNU MP) 

素数一覧 1000万 

素数表 

素数を判定するプログラムを書いていきます。

単純にC言語で書いたのがコレ。

//$ gcc prime1.c -o prime1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int isPrime(unsigned long number)
{
int i;
for (i = 2; i < number; i++) {
if (number % i == 0) {
return 0;
}
}
return 1;
}

int main(void)
{
unsigned long number = 9999991;
int answer = 0;
answer = isPrime(number);
if (answer) {
printf("%lu は素数だよ\n", number);
} else {
printf("%lu は素数じゃないよ\n", number);
}
return 0;
}

numberのところに判定する数字を入力してください。

3箇所アルゴリズムを改良して早くしていきます。 

1. まず2や3で割り切れるなら素数ではありません。
 候補ではない数字を最初に除外します。これをエラトステネスの篩といいます。

2. 判定する数字を最後までチェックする必要はありません。
 判定する数字を2つの積で表します。
 たとえば100を2つの積で表してみましょう。
 2 * 50     2で素数かどうかチェック済み
    4 * 25 4で素数かどうかチェック済み
    5 * 20 5で素数かどうかチェック済み
   10 * 10 10で素数かどうかチェック済み

 つまりわざわざ100まで調べなくても良いのです。100のルートを取り10を上限とします。
 素数かどうかを調べるには10以下まで調べれば良いです。
  
3. 素数の数字に注目する。
 5以上100までの素数を書いてみます。
 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
 素数というのは6の倍数の隣の数字になります。確認してください。
 6k ± 1で表せます。

 この3つを考慮してプログラムを書くと次になります。

//$ gcc prime2.c -o prime2

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int isPrime(unsigned long number)
{
unsigned int i;
if (number <= 3 && number > 1) {
return 1;
} else if (number % 2 == 0 || number % 3 == 0) {
return 0;
} else {
for (i = 5; i * i <= number; i += 6) {
if (number % i == 0 || number % (i + 2) == 0) {
return 0;
}
}
}
return 1;
}

int main(void)
{
unsigned long number = 9999991;
int answer = 0;
answer = isPrime(number);
if (answer) {
printf("%lu は素数だよ\n", number);
} else {
printf("%lu は素数じゃないよ\n", number);
}
return 0;
}


これでだいぶ早くなったはずです。
for分がややこしいかもしれませんが、一度紙に書いてトレースして確認してみてください。
 
次回はGMPライブラリーを使って素数判定プログラムに改良していきます。

素数判定プログラム C言語 GMPライブラリー


Raspberry Piに初音ミクの声でしゃべらせよう。

もちろんウェブからコントロールできるようにします。

21世紀的ですね。

必要なものはOpen Jtalk と初音ミクの声データ。

$ sudo apt-get install open-jtalk open-jtalk-mecab-naist-jdic htsengine libhtsengine-dev hts-voice-nitech-jp-atr503-m001

以下のサイトを参考にしてください。
jsay スクリプトを保存して

$ sudo chmod +x jsay
$ sudo cp jsay /usr/bin/


MMDAgend Example-1.3.1をダウンロード

$ unzip MMDAgend_Example-1.3.1.zip
$ sudo cp -R MMDAgend_Example-.1.3.1/Voice/* /usr/share/hts-voice/

これで話すようになります。
$ jsay こんにちわ

今度は初音ミクの声をダウンロードしましょう。

ここからTYPE-βの方をダウンロード 解凍して声データを
/usr/share/hts-voice/mei_happy/
に上書きしてください。

初音ミクの声で話すようになります。

私の環境ではhttp://192.168.0.101/miku/
にindex.phpを置いてウェブからコントロールできるようにしています。


<?php
//Miku Talk

if($_POST["talk"]) {
exec("jsay ".$_POST["talk"]);
}
?>

<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Miku Talk</title>
<link rel="stylesheet"
  href="http://code.jquery.com/mobile/1.4.2/jquery.mobile-1.4.2.min.css" />
<script src="http://code.jquery.com/jquery-1.11.1.min.js"></script>
<script src="http://code.jquery.com/mobile/1.4.2/jquery.mobile-1.4.2.min.js">
</script>

<style type="text/css">  
<!-- 
    #header, #footer {
          background-color: #f09199;
color: #ebf6f7;
}
-->  
</style>
</head>
<body>
<div data-role="page">
  <div data-role="header" id="header">
    <h1>Miku Talk</h1>
  </div>
  <div role="main" class="ui-content">
    

<form action="index.php" method="post">
  
  しゃべる内容:<br />
  <textarea name="talk" cols="30" rows="5"></textarea><br />
  <br />
  <input type="submit" value="しゃべる" />
</form>


  </div>
  <div data-role="footer" id="footer">
    <h3><a href="http://www.nakatayuki.com/" >nakata yuki</a></h3>
  </div>
</div>
</body>
</html>


参考サイト


サプリメントを健康のために摂っていますか?

サプリメントの不都合な真実。

サプリメントはほとんど添加物でできているのです。

私が飲んでいるネイチャーメイドのスーパーマルチビタミン&ミネラルの添加物を計算してみましょう。

5分もあれば計算できますよ。

1錠 1.515gです。

栄養成分
タンパク質:0~0.1g
脂質:0~0.1g
炭水化物:0.67g
ナトリウム:0~2mg
カルシウム:200mg
マグネシウム:100mg
亜鉛:6mg
鉄:4mg
銅:0.6mg
セレン:50µg
クロム:20µg
ビタミンA:300µg
β-カロテン:1.8mg
ビタミンB1:1.5mg
ビタミンB2:1.7mg
ビタミンB6:2mg
ビタミンB12:3µg
ナイアシン:15mg
パントテン酸:6mg
葉酸:240µg
ビオチン:50µg
ビタミンC:125mg
ビタミンD:10µg
ビタミンE:9mg

この中で欲しいのはナトリウム以下です。タンパク質、脂質、炭水化物を除外します。

あとは足してください。googleかyahooに計算してもらえば一瞬で終わります。

2mg +  200mg + 100mg + 6mg + 4mg + 0.6mg + 50µg + 20µg + 300µg + 1.8mg + 1.5mg + 1.7mg + 2mg + 3µg + 15mg + 6mg + 240µg + 50µg + 125mg + 10µg + 9mg

http://search.yahoo.co.jp/search?p=2mg+%2B++200mg+%2B+100mg+%2B+6mg+%2B+4mg+%2B+0.6mg+%2B+50%C2%B5g+%2B+20%C2%B5g+%2B+300%C2%B5g+%2B+1.8mg+%2B+1.5mg+%2B+1.7mg+%2B+2mg+%2B+3%C2%B5g+%2B+15mg+%2B+6mg+%2B+240%C2%B5g+%2B+50%C2%B5g+%2B+125mg+%2B+10%C2%B5g+%2B+9mg&aq=-1&oq=&ei=UTF-8&fr=top_ga1_sa&x=wrt&clr=1


計算結果は475.27300 milligrams となりました。つまり0.475gです。

栄養素は 0.475 * 100 / 1.515 = 31%

栄養素はたったの31%ですよ。約30%

残りの70%は添加物となります。

1000円で購入したとしたら700円で添加物を購入していることになります。

そこまでして自分に必要なものなのかを考えてから購入しましょう。 


Loackerのウエハースです。

ウエハースといえばローカー。ローカーといえばウエハース。

ショートニングが入っていません。

それだけではなく人口着色料、遺伝子組み換え、保存料は一切使用していません。

このウエハースだけではなく、メーカーとしてそういうものは一切入れていません。

頼もしいです。

高級スーパーでよく売っています。

好きな味はダークチョコレートとバニラ。甘さ控えめなのが好きです。

ティラミス味は?ってかんじ。

単純にココアパウダーとマルカポーネチーズの味が弱いので、ティラミスと言われないとわからないかも。


しつこいですが、ショートニングや不飽和脂肪酸は極力摂るのを止めましょう。

心臓病や心筋梗塞の原因になりますよ。




 
ショートニングの入っていないお菓子1 コペンハーゲンのミニクッキー 


 フィボナッチ数列を計算してみよう1 C言語 の続きです。

前回はC言語だけでフィボナッチ数列を計算していました。

それだけだとunsigned long型の上限があり、大きな数字が計算できません。

今回はgmpライブラリを使ってフィボナッチ数列 1000001番目を計算してみます。

fibo.cというファイル名で保存してください。 

//gcc fibo.c -o fibo -lgmp
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <gmp.h>

void omg_i_love_leonardo_of_pisa(uint32_t num, mpz_t * result) 
mpz_t retval, last, tmp;
mpz_init(retval);
  mpz_init(last);
mpz_init(tmp);

uint32_t i = 1;
if(num == 0) {
return;
}
  mpz_set_ui(retval, 1U);
mpz_set_ui(last, 0U);

for(; i < num; i++) {
mpz_set(tmp, retval);
mpz_add(retval, retval, last);

mpz_set(last, tmp);
}

mpz_set(*result, retval);
 }

int main() 
{
uint32_t num;
mpz_t fibo;
mpz_init(fibo);

//1000001
omg_i_love_leonardo_of_pisa(1000001, &fibo);
mpz_out_str(stdout, 10, fibo);
printf("\n");
return 1;
}

$ gcc fibo.c -o fibo -lgmp
$ ./fibo

すぐに計算結果が出てきます。
科学技術すげー。

http://www.wolframalpha.com/input/?i=fibonacci+1000001


実はgmpにはmpz_fib_uiというフィボナッチ関数が用意されています。
mpz_fib_ui関数を実行するだけフィボナッチ数列を求めることができます。

fibo3.cというファイル名で保存してください。
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <gmp.h>

int main()
{
  int n = 1000000;
  mpz_t fm2;
  mpz_inits(fm2, NULL);
  mpz_fib_ui(fm2, n);
  gmp_printf("fib(%d) = %Zd\n", n, fm2);
  return 1;
}
 
$ gcc fibo3.c -o fibo3 -lgmp
$ ./fibo3
 
参考サイト
1,000,000th Fibonacci Number One-Liner in C

↑このページのトップヘ