PICマイコンに素数を計算させてみた

今回は、下の動画にあるようにPICマイコンに無理やり素数探索をしてもらいました。かわいそう。



用意するもの

素数判定プログラムを作る

素数とは

素数とは、その数自身と1以外に因数を持たない数のことを言います。例えば5を割れるのは5か1だけになりますね。これは素数です。ですが、例えば6は2でも3でも割れるので素数ではありません。

素数にはある程度ランダム性があり、N番目の素数をNで表す式は今のところありません。これが、東工大生に愛される所以かも知れません。

では、どのように素数を見つければいいのでしょうか

素数判定プログラム

ある数iが素数であることを示すには、2~i-1までの数字でiが割れるかを順に確かめるしかありません。特に法則性はありませんからね。簡単なプログラムを書いてみると、


      int findPrime(int i){   //素数ならば0,そうでないなら1を返す関数
        int j, k=0;
        for(j=2;j<i-1;j++){   //jを2~i-1までカウントアップ
          if(i%j==0){         //もしi/jの余りが0、つまり割り切れた場合
            k=1;
            break;
          }
        }
        return k;
      }
    

となります。iが5の場合、jは2~4までの数字でiを割ろうとしますが、どれも余りは0ではありません。よって、kは0のままで、素数であることが確かめられます。では、これをマイコンのPICに無理やり計算させてみましょう。コンピュータは元々計算機ですからね!がんばれPIC!

完成プログラム

今回は、素数を順にLCDに表示していきます。I2C接続LCDの使い方を参考に、回路を組んでください。今回は、PICに繋ぐものはLCDだけです。


      // PIC16F1938 Configuration Bit Settings

          // 'C' source line config statements

          // CONFIG1
          #pragma config FOSC = INTOSC    // Oscillator Selection (INTOSC oscillator: I/O function on CLKIN pin)
          #pragma config WDTE = OFF       // Watchdog Timer Enable (WDT disabled)
          #pragma config PWRTE = OFF      // Power-up Timer Enable (PWRT disabled)
          #pragma config MCLRE = OFF      // MCLR Pin Function Select (MCLR/VPP pin function is digital input)
          #pragma config CP = OFF         // Flash Program Memory Code Protection (Program memory code protection is disabled)
          #pragma config CPD = OFF        // Data Memory Code Protection (Data memory code protection is disabled)
          #pragma config BOREN = OFF      // Brown-out Reset Enable (Brown-out Reset disabled)
          #pragma config CLKOUTEN = OFF   // Clock Out Enable (CLKOUT function is disabled. I/O or oscillator function on the CLKOUT pin)
          #pragma config IESO = OFF       // Internal/External Switchover (Internal/External Switchover mode is disabled)
          #pragma config FCMEN = OFF      // Fail-Safe Clock Monitor Enable (Fail-Safe Clock Monitor is disabled)

          // CONFIG2
          #pragma config WRT = OFF        // Flash Memory Self-Write Protection (Write protection off)
          #pragma config VCAPEN = OFF     // Voltage Regulator Capacitor Enable (All VCAP pin functionality is disabled)
          #pragma config PLLEN = ON// PLL Enable (4x PLL disabled)
          #pragma config STVREN = ON      // Stack Overflow/Underflow Reset Enable (Stack Overflow or Underflow will cause a Reset)
          #pragma config BORV = LO        // Brown-out Reset Voltage Selection (Brown-out Reset Voltage (Vbor), low trip point selected.)
          #pragma config LVP = ON         // Low-Voltage Programming Enable (Low-voltage programming enabled)

          // #pragma config statements should precede project file includes.
          // Use project enums instead of #define for ON and OFF.

          #include <xc.h>
          #include <pic16f1938.h>
          #include <math.h>
          #include <stdio.h>
          #define _XTAL_FREQ 32000000
          #define LCD_ADD 0x7C

          void I2C_Master_Init(const unsigned long c)
          {
            SSPCON1 = 0b00101000;
            SSPCON2 = 0;
            SSPADD = (_XTAL_FREQ/(4*c))-1;
            SSPSTAT = 0b00000000 ;    // 標準速度モードに設定する(100kHz)
          }

          void I2C_Master_Wait()
          {
            while ((SSPSTAT & 0x04) || (SSPCON2 & 0x1F));
          }

          void I2C_Master_Start()
          {
            I2C_Master_Wait();
            SEN = 1;
          }

          void I2C_Master_RepeatedStart()
          {
            I2C_Master_Wait();
            RSEN = 1;
          }

          void I2C_Master_Stop()
          {
            I2C_Master_Wait();
            PEN = 1;
          }

          void I2C_Master_Write(unsigned d)
          {
            I2C_Master_Wait();
            SSPBUF = d;
          }
          void writeData(char t_data){
              I2C_Master_Start();
              I2C_Master_Write(LCD_ADD);
              I2C_Master_Write(0x40);
              I2C_Master_Write(t_data);
              I2C_Master_Stop();
              __delay_ms(10);
          }
          void writeCommand(char t_command){
              I2C_Master_Start();
              I2C_Master_Write(LCD_ADD);
              I2C_Master_Write(0x00);
              I2C_Master_Write(t_command);
              I2C_Master_Stop();
              __delay_ms(10);
          }
          void PICinit(){
            OSCCON = 0b01110000;
            ANSELA = 0b00000000;
            ANSELB = 0b00000000;
            TRISA  = 0b00000000;
            TRISB  = 0b00000000;
            TRISC  = 0b00011000;
            PORTA  = 0b00000000;    //2進数で書いた場合
            PORTB  = 0x00;          //16進数で書いた場合
          }
          void LCD_Init(){            //LCDの初期化
            I2C_Master_Init(100000);
            __delay_ms(400);
            writeCommand(0x38);
            __delay_ms(20);
            writeCommand(0x39);
            __delay_ms(20);
            writeCommand(0x14);
            __delay_ms(20);
            writeCommand(0x73);
            __delay_ms(20);
            writeCommand(0x52);
            __delay_ms(20);
            writeCommand(0x6C);
            __delay_ms(250);
            writeCommand(0x38);
            __delay_ms(20);
            writeCommand(0x01);
            __delay_ms(20);
            writeCommand(0x0C);
            __delay_ms(20);
          }

          void LCD_str(char *c) {     //LCDに配列の文字を表示
            unsigned char i,wk;
            for (i=0 ; ; i++) {
              wk = c[i];
              if  (wk == 0x00) {break;}
              writeData(wk);
            }
          }


          int main(void){
            PICinit();      //PICを初期化
            LCD_Init();

            char prime[16];
            writeCommand(0x02);   //ホームへカーソル移動
            int i,j,k;

            sprintf(prime,"PrimeNum:2");
            LCD_str(prime);               //LCDに最初の素数2を表示
            for(i=3;i<=10000;i+=2){
      		    k=0;                        //素数判定変数をリセット
      		    for(j=3;j<=sqrt(i);j+=2)    //jは割る数で、iの平方根までカウントアップ
      		    {
      			    if(i%j==0)              //もしjで割れた場合(つまり、素数じゃない場合)
      			    {
      				    k=1;                //素数判定変数に1を代入
      				    break;              //ループ離脱
      			    }
      		    }

      		    if(k==0){                   //素数の場合
                  sprintf(prime,"PrimeNum:%d",i);     //primeに文字列"PrimeNum:i"をセット
                  writeCommand(0x02);   //ホームへカーソル移動
                  LCD_str(prime);                     //LCDに文字列primeを表示
              }
            }

          }
    

今回は性能を最大限に引き出すべく、32MHzで駆動しています。configのPLLENをONにすれば、クロック周波数は4倍になるので、OSCCONが8MHz設定になっていれば32MHz駆動となります。何を言っているのかわからない方はPICのプログラムの基本構成をご覧ください。

上のLCD関連の関数は先程示したI2C接続LCDの使い方に詳しくあるので割愛します。

では、main関数を見ていきましょう。よく見ると、先程示したアルゴリズムと若干異なっていることが分かります。for文の中を見てください。iは3からスタートし、2ずつカウントアップしています。これは、偶数は素数ではないことを利用した高速化です。当たり前ですが、偶数は2の倍数なので素数ではないですね。よって、3,5,7,9…とiを増やして割れるかどうか確かめるわけです。

ここからは同じです。割れてしまった場合はkに1を代入して、ループを抜けます。

抜けた先の処理を見てみましょう。


      if(k==0){                   //素数の場合
          sprintf(prime,"PrimeNum:%d",i);     //primeに文字列"PrimeNum:i"をセット
          writeCommand(0x02);   //ホームへカーソル移動
          LCD_str(prime);                     //LCDに文字列primeを表示
      }
    

sprintf関数は、第一引数の配列に第二引数の文字列を代入する関数です。printfの表示を変数の代入に置き換えたものだと思えばOKですね。printfと同じように%dを使い、それに当てはまる変数を第三引数に置きます。これで、例えばi=7の場合にはPrimeNum:7と画面に表示されるわけです。その後、カーソルをホームに戻せば、次素数が見つかった時に上書きされます。

発展・他のアイデア

本来LEDをオンオフしたり、LCDに表示させたり、センサーの値を読み取ったりするのがマイコンの役割ですので、こんな使い方に発展もクソもありません。

強いて言えば、完全数を計算→LCDに表示等でしょうか(パソコンでやれよ)。

また、素数はある程度のランダム性がありますから、素数が見つかったらスピーカーの音が短い時間鳴るという装置も作れるかもしれません(スピーカーの使い方(PIC16F1938))。もはやアートですね。

後は、素数当てクイズとかどうでしょうか。PICが無作為に選んだ数をLCDに表示し、私たちが直感で素数だと思ったら赤のボタンを、違うと思ったら青のボタンを押し、その後素数判定→正解ならLED点灯…の繰り返しなど。こうすれば、段々と素数を覚えていけるのではないでしょうか!

と、長々と書いてしまいましたが、PICはあんまりいじめないように。こんな記事を読んでくれてありがとうございました。


「PICマイコンに素数を計算させてみた」に2件のコメントがあります

  1. ピンバック: Wak-tech » 素数の音を聴く【PICマイコン】

  2. ピンバック: 素数の音を聴く【PICマイコン】 | Wak-tech

コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です