C/C++ GMP ライブラリを使う（Java でいう BigInteger です)

とても大きな数を扱うとき、Java では BigInteger などを使うと制限なしです。しかも標準装備。

ここで扱いたい大きな数というのは、ほかでもないメルセンヌ素数です。とんでもなく大きな数となるのでどうしてもライブラリを使う必要があります。

ほかでもないというのは、メルセンヌ素数という形であれば素数であるかの判定が容易という理由から、発見された最大の素数はメルセンヌ素数であるからです。

	// Mersenne.java -- Calculate Mersenne prime number
	// Copyright (c) 2016 easai
	// Author: easai
	// Created: Wed Jun 29 20:56:11 2016
	// Keywords:
	// Commentary:
	// Compile as (does not require any additional library):
	// javac Mersenne.java
	//
	// Run as:
	// java Mersenne n
	// Code:
	import java.math.*;
	import java.io.*;
	public class Mersenne
	{
	public static BigInteger mersenne(int p)
	{
	return (BigInteger.ONE.shiftLeft(p)).subtract(BigInteger.ONE);
	}
	public static void main(String args[])
	{
	int n=1;
	try
	{
	if(args.length==0)
	{
	System.out.print("Enter a number: ");
	BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
	String str=reader.readLine();
	n=Integer.parseInt(str);
	}
	else
	{
	n=Integer.parseInt(args[0]);
	}
	BigInteger mp=mersenne(n);
	System.out.println(mp);
	}
	catch(Exception e){e.printStackTrace();}
	}
	}
	// Mersenne.java ends here

view raw Mersenne.java hosted with ❤ by GitHub

このプログラムをCで実装しようとすると、GMPなど外部ライブラリが必要となります。GMPを使ったソースです。

	// mersenne.cpp -- Calculate Mersenne prime number
	// Copyright (c) 2016 easai
	// Author: easai
	// Created: Wed Jun 29 20:53:34 2016
	// Keywords:
	// Commentary:
	//
	// Compile as (requires gmp library):
	// gcc mersenne.c -lgmp
	//
	// Code:
	#include <stdlib.h>
	#include <stdio.h>
	#include <unistd.h>
	#include <gmp.h>
	void mersenne(mpz_t r, int p)
	{
	mpz_ui_pow_ui(r,2,p);
	mpz_sub_ui(r,r,1);
	}
	int main(int argc, char* argv[])
	{
	int nopt=0;
	char *nparam=NULL;
	int opt;
	while((opt=getopt(argc, argv, "h"))!=-1) {
	switch(opt){
	case 'h':
	printf("Usage: mersenne n\n");
	break;
	}
	}
	int n;
	if(optind < argc)
	{
	n=atoi(argv[optind]);
	mpz_t t;
	mpz_init(t);
	mersenne(t,n);
	gmp_printf("%Zd \n",t);
	mpz_clear(t);
	}
	return 0;
	}
	// mersenne.cpp ends here

view raw mersenne.c hosted with ❤ by GitHub

このプログラムもC++を使うと分かりやすくなります。初期化、後始末などコンストラクタ、デストラクタで書けるからです。

	// mersenne.cpp -- Calculate Mersenne prime number
	// Copyright (c) 2016 easai
	// Author: easai
	// Created: Wed Jun 29 20:53:34 2016
	// Keywords:
	// Commentary:
	//
	// Compile as (requires gmp library):
	// g++ mersenne.cpp -lgmpxx -lgmp
	//
	// Code:
	#include <unistd.h>
	#include <gmpxx.h>
	#include <iostream>
	using namespace std;
	mpz_class mersenne(int p)
	{
	mpz_class mp;
	mpz_ui_pow_ui(mp.get_mpz_t(),2,p);
	mp--;
	return mp;
	}
	int main(int argc, char* argv[])
	{
	int nopt=0;
	char *nparam=NULL;
	int opt;
	while((opt=getopt(argc, argv, "h"))!=-1) {
	switch(opt){
	case 'h':
	printf("Usage: mersenne n\n");
	break;
	}
	}
	int n;
	if(optind < argc)
	{
	n=atoi(argv[optind]);
	mpz_class mp=mersenne(n);
	cout << mp;
	}
	return 0;
	}
	// mersenne.cpp ends here

view raw mersenne.cpp hosted with ❤ by GitHub

C#だとこんな感じでしょうか。

	// Mersenne.cs -- Calculate Mersenne prime number
	// Copyright (c) 2016 easai
	// Author: easai
	// Created: Wed Jun 29 20:53:34 2016
	// Keywords:
	// Commentary:
	//
	// Tested with VC++ 2015
	//
	// Code:
	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	using System.Numerics;
	namespace Prime
	{
	class Program
	{
	static BigInteger mersenne(int p)
	{
	BigInteger mp = 1;
	mp = (mp << p) - 1;
	return mp;
	}
	public static bool isPrime(BigInteger n)
	{
	bool isPrime = true;
	BigInteger max = n;
	BigInteger i = 1;
	while (i < max)
	{
	if (i != 1 && (n % i) == 0)
	{
	isPrime = false;
	break;
	}
	max = n / i;
	i++;
	}
	return isPrime;
	}
	static void Main(string[] args)
	{
	int[] p = { 2, 3, 5, 7, 13, 17, 19, 31 };
	for(int i=0;i<p.Length;i++)
	{
	BigInteger mp=mersenne(p[i]);
	if (isPrime(mp))
	Console.WriteLine(mp + " is a prime");
	else
	Console.WriteLine(mp + " is not a prime");
	}
	}
	}
	}
	// Mersenne.cs ends here

view raw Mersenne.cs hosted with ❤ by GitHub

Arduino ISP: ATTiny13A でサイコロを回す

ATtiny13A でサイコロを回そうと思えば rand() 関数が大きいようです。ここは自分で組まねばなりません。

乱数といえば線形合同法だと思えば、Xorshift なる計算方法が流行ってるんですねえ。

高速かつ長周期、じゃあということで Xorshift へ乗り換えて作ってみました。

マシンで合成する疑似乱数ってのは「疑似」乱数なのであってパターンが決まっています。ある一定の周期を持つわけです。長ければ長いほどいい乱数です。あとは出てくる値が均一でないとなりません。

メルセンヌ・ツイスタをすすめる向きもあるようですが、ここでは Xorshift で。

あとシードが必要なんですが、タイマーを使ったりメモリを読んだり、空ピンの値を読んだりするのがベスト・プラクティスなようです。ここではスイッチでの割り込み時のカウンタの値を使ってみました。

	/*
	* Dice.cpp
	*
	* Created: 2016-06-21
	* Author : easai
	*/
	#include <avr/io.h>
	#include <avr/interrupt.h>
	int digit[6] = {
	0b10000,
	0b01000,
	0b11000,
	0b01100,
	0b11100,
	0b01101
	};
	volatile unsigned long r;
	volatile unsigned long timer_counter=0;
	int interval=1000;
	volatile unsigned int counter=0;
	ISR(TIM0_OVF_vect)
	{
	timer_counter++;
	if((timer_counter%interval)==0)
	{
	if(counter < 50)
	{
	// Xorshift
	r = r ^ (r << 13);
	r = r ^ (r >> 17);
	r = r ^ (r << 5);
	// LCG
	// r=(r*109+89)%251;
	PORTB = digit[r%6];
	counter++;
	}
	else if(counter < 100)
	{
	PORTB = digit[r%6];
	counter++;
	}
	else
	{
	PORTB = 0;
	}
	}
	}
	ISR(INT0_vect)
	{
	cli();
	counter=0;
	r=timer_counter;
	sei();
	}
	int main(void)
	{
	DDRB |= 0b11101;
	PORTB = 0;
	TCCR0A=0;
	TCCR0B=(1<<CS00);
	TIMSK0|=(1<<TOIE0);
	MCUCR |= (1<<ISC01);
	GIMSK |= (1<<INT0);
	sei();
	timer_counter=0;
	counter=100;
	while (1) {}
	}

view raw Dice.cpp hosted with ❤ by GitHub

Imref とは？（フェルミ準位の話です）

英国のEU脱退の話ですね？

EUが崩壊するのか、英国が崩壊するのか。西洋社会が崩壊するのか。

世界経済が崩壊するとなんですがね。

規制緩和、プライマリーバランス。官僚の無駄遣い。よく理解できますよね。EUってのね。

しかしですよ、英国がEU脱退すると影響力とかってなくなるわけですよね。

突っ走るEUとか、米国のポチと成り果てる英国とか。

閑話休題。

オンラインで電子工学の授業を視聴していたら、imref って単語が出てきました。

新しい単位でも定義したのかと思うと、この単語よくよく見てみると...

Fermi だっていうんですよ。フェルミ準位の Fermi です。で、imref が何かといえばこの Fermi の逆。逆読みだっていうんですね。

分からないものですね。一見まったく別の単語としか見えない。疑フェルミ準位を表すものだそうです。不純物が入るとフェルミ準位がずれるのでその値です。

ということで、文字を反転するプログラムを書いてみました。

まずは Elisp で。

	(defun reverse-word(str)
	"Reverse the given string"
	(interactive "sWord:")
	(eval (cons 'concat (reverse (mapcar (lambda(x) (string x)) str)))))
	;(reverse-word "fermi")
	(defun _reverse(lst)
	"Reverse the given list"
	(if (= (length lst) 1)
	lst
	(append (_reverse (cdr lst)) (list (car lst)))))
	;(_reverse '( a b c d e))
	(defun reverse-region(start end)
	"Reverse text in the region"
	(interactive "r")
	(insert (reverse-word (buffer-substring-no-properties start end)))
	(kill-region start end))
	;edcba
	;(apply 'string (scramble "abcdef"))
	(defun scramble (str)
	"Scramble the word specified"
	(shuffle-list str))
	(defun shuffle-list (str)
	"Return random ordered list."
	(let* ((lst (string-to-list str))
	(len (length lst))
	(r (random len)))
	(if (< len 1)
	nil
	(cons (nth r lst)
	(scramble (append (head r lst)(nthcdr (1+ r) lst)))))))

view raw scrambled.el hosted with ❤ by GitHub

こちらは C++(g++)。

	#include<string>
	#include<iostream>
	using namespace std;
	int main()
	{
	string str;
	cout << "Enter a word: ";
	cin >> str;
	int n=str.length();
	for(int i=0;i<n;i++)
	{
	cout << str[n-i-1];
	}
	cout << endl;
	return 0;
	}

view raw reverse.cpp hosted with ❤ by GitHub

ついでといえばなんですが、じゃあということで反転だけじゃなくて文字列をスクランブルするプログラムを書いてみました。

	#include <climits>
	#include <cstdlib>
	#include <iostream>
	#include <unistd.h>
	using namespace std;
	string scramble(string str)
	{
	int n=str.length();
	string res="";
	int filled[n];
	for(int i=0;i<n;i++)
	filled[i]=0;
	for(int i=0;i<n;i++) {
	int r=rand() % (n-i);
	int j=0;
	int count=0;
	do {
	if(filled[j]==0) {
	if(r<=count) {
	filled[j]=1;
	break;
	}
	count++;
	}
	}
	while(++j<n);
	res+=str[j];
	}
	return res;
	}
	long factorial(int n)
	{
	long res;
	if(n==1)
	res=n;
	else
	res=n*factorial(n-1);
	return res;
	}
	int main(int argc, char* argv[])
	{
	string str;
	srand(time(NULL));
	int nopt=0;
	char *nparam=NULL;
	int opt;
	while((opt=getopt(argc, argv, "n:"))!=-1) {
	switch(opt){
	case 'n':
	nopt=1;
	nparam=optarg;
	break;
	}
	}
	int n=INT_MAX;
	if(nopt==1)
	{
	n=atoi(nparam);
	}
	if(optind < argc)
	{
	str=scramble(argv[optind]);
	}
	else
	{
	cout << "Enter a word: ";
	cin >> str;
	}
	int len=str.length();
	int n_res=min((int)factorial(len),n);
	string resList[n_res];
	for(int i=0;i<n_res;i++)
	{
	bool duplicate=true;
	string new_str="";
	while(duplicate){
	new_str=scramble(str);
	duplicate=false;
	for(int a=0;a<i;a++)
	{
	if(resList[a].compare(new_str)==0)
	{
	duplicate=true;
	break;
	}
	}
	}
	resList[i]=new_str;
	}
	for(int i=0;i<n_res;i++)
	cout << resList[i] << endl;
	return 0;
	}

view raw scramble.cpp hosted with ❤ by GitHub

乱数を計算する回数を減らすよう乱数を出してからはじくのではなく、必要な分だけ計算し文字列から選んでいます。

Arduino ISP: ATtiny 割り込み・PWM

Arduino ISP を使うと ATtiny13A をそのままプログラムできます。そのままというのは、Arduino IDE を介さないでってことです。ライブラリを使わず書くと、プログラムサイズを小さくできます。

pinMode(), digitalWrite() などは使えず、マイクロコントローラのレジスタなど設定せねばなりません。pinMode() は DDRB レジスタ、digitalWrite() は PORTB などのレジスタを設定することで実装できます。

割り込みなどは MCUCR, GIMSK レジスタを設定し、割り込みを許可せねばなりません。

	/*
	* Interrupt.cpp
	*
	* Created: 6/2/2016 5:05:28 PM
	* Author : easai
	*/
	#define F_CPU 1000000UL
	#include <avr/io.h>
	#include <avr/interrupt.h>
	#include <util/delay.h>
	ISR(INT0_vect)
	{
	PORTB |= (1<< DDB0);
	_delay_ms(10000);
	PORTB &= ~(1<< DDB0);
	}
	int main(void)
	{
	DDRB |= (1<<DDB0);
	MCUCR |= (1<<ISC01);
	GIMSK |= (1<<INT0);
	sei();
	while (1){}
	return 0;
	}

view raw Interrupt.cpp hosted with ❤ by GitHub

参照：ピン入力と割り込み


ATtiny13A では PWM 出力が可能ですが、これも TCCR0A, TCCR0B レジスタを設定し、デューティ比を OCR0A, OCR0B などで設定します。

	/*
	* PWM.cpp
	*
	* Created: 6/3/2016 8:59:58 AM
	* Author : easai
	*/
	#define F_CPU 1000000UL
	#include <avr/io.h>
	#include <util/delay.h>
	int main(void)
	{
	DDRB |= 0b00011;
	TCCR0A = (1<<COM0A1) | (1<< COM0B0) | (1<< COM0B1) | (1 << WGM01) | (1 << WGM00);
	OCR0A = 0;
	OCR0B=0;
	TCCR0B = (1<<CS00);
	while (1)
	{
	OCR0A+=10;
	if(255<=OCR0A)
	{
	OCR0A=0;
	}
	OCR0B=OCR0A;
	_delay_ms(500);
	}
	return 0;
	}

view raw PWM.cpp hosted with ❤ by GitHub

参照：PWMについて調べて、リモコン信号出力してみた。（ATtiny13A）　


ATtiny13A の良さといえば、省電力で省スペース、低価格であること。活用しましょう。