多倍長計算

[TTP]

ABを使わせてもらっています。
質問なんですが、ABで多倍長計算（メモリの許す限りどこまでも計算できる）
を使うことはできませんか？
インターネットで調べても、C/C++のコードしか出てきません。
あと、四則演算が使えれば十分です。

[konisi]

今丁度、色々調べて文書化しているところです。

んーと、引き算は面倒なのでまだまとめてませんが、足し算、掛け算、割り算、累乗算などは一応教えることが出来ます。

んでも結構ソース複雑になりますよ。標準装備されてないだけあって。
教えましょうか?

[TTP]

ありがとうございます！是非お願いします。

[konisi]

一応例があったほうがやりやすいので、例を提示したいと思うのですが、無理数とかを「小数点以下何万桁」とかそういう風に正確に求める目的で多倍長計算を使うのか、累乗・階乗計算等のようにとても大きな数を扱う為に多倍長計算を使うのかによってデータの入れ方がちょっとだけ違いますので（厳密に言えば、「ちょっと」ではなくて順番が逆なんですけどね。）それを後でレスしてください。一応今考え方だけ書きますので。

多倍長計算って言うのは簡単に言うと、「一つの変数で表しきれないなら二つ三つ使って表しちまえ」っていう考え方になります。データの順番を変える理由は、掛け算をするときに桁の位置の計算が楽になるからってだけなんですけど、プログラム自体は人間が書いていくので識別した方が分りやすいかと思います。

（My覚書より引用）
定義
　ビックエンディアン：位の大きい方から変数やフィールドに詰めていく方式
　リトルエンディアン：位の小さい方から変数やフィールドに詰めていく方式

つまり、Word型二つで数値12345678をビックエンディアンとして定義すると

Dim tA[1]=(1234,5678)

リトルエンディアンとして定義すると

Dim tA[1]=(5678,1234)

のようになる。（実際にはもっとつめて表現できるが、分りにくくなる為完全な10進数表記とした。）

分りにくいところがあったら質問してくださいね。

[TTP]

返信遅くなってすみません。
今回扱いたいのは、大きな数です。

[konisi]

大きな数ですか。
小数も同時に扱いますか?

小数を扱わないやつなら今からでも関数群作って楽に操作できるようにしますが。

[konisi]

数学について良く知っている人で、なおかつカンが物凄くいい人ならもう気付いているかもしれませんが、「何故データを入れる順番を逆にする必要があるのか」について書いておきます。

簡単に言ってしまえば、多倍長計算で扱っている配列同士を掛け算する時に代入先のケタの位置を考える必要性があり、順番が逆になると桁の位置の計算が凄く面倒になるのです＾＾；(下図参照）

　　　A1　A2　A3
×　　B1　B2　B3
---------------
　　　X　 X　 X
　 X　X　 X　　←桁がずれる
X　X　X　　　　←桁がずれる
---------------
Y　Y　Y　 Y　 Y
　

このため、大きな数を扱う時は位の低い数から配列に詰めて行き、小さな少数を扱う時は位の大きい数から配列に詰めて行きます。（と言うか、その方が組みやすいってだけで理論上はどちらを使っても組むことは可能ですが。）

[TTP]

すみません、返信したつもりだったんですが、うまくできなかったのにそのまま確認せずに電源を切ってしまっていました。
一応、少数は基本的に扱いません。
よろしくお願いします。

[konisi]

面倒なので各関数の使用方法などは後述。

関数群のコード↓（注:まだバグフィッシュが完全では無い可能性あり。）

コード: 全て選択

Sub Syokika(A As *Word,B As Word)(C As Long)
	Dim i As Long
	if C=0 then
		C=Keta
	End If
	for i=0 to C
		A(i)=B
	Next i
End Sub

Sub Ireru(A As *Word,B As *Word)
	Dim i As Long
	For i=0 To Keta
		A(i)=B(i)
	Next i
End Sub

Sub Ireru_l(A As *Word,B As *Long)
	Dim i As Long
	For i=0 To Keta
		A(i)=B(i) As Word
	Next i
End Sub

Sub Ireru_dw(A As *Word,B As *DWord)
	Dim i As Long
	For i=0 To Keta
		A(i)=B(i) As Word
	Next i
End Sub

Sub Ireru_w(A As *Word,B As *Word)
	Ireru(A,B)
End Sub

Sub Hikaku(A As *Word,B As *Word,ByRef K As Long)(ByRef L As Long)
	Dim i As Long
	For i=Keta To 0 Step -1
		if A(i)>B(i) then
			K=1
			L=i+1
			Exit Sub
		Elseif A(i)<B(i) then
			K=-1
			L=i+1
			Exit Sub
		End If
	Next i
	K=0
	L=0
End Sub

Sub Kuriagari_w(A As *Word)
	Dim i As Long
	For i=0 To Keta
		if A(i)>Max then
			A(i+1)=A(i+1)+Fix(A(i)/Max)
			A(i)=A(i)-Fix(A(i)/Max)*Max
		End If
	Next i
End Sub

Sub Kuriagari_dw(A As *DWord)(B As Long)
	Dim i As Long
	if B=0 then
		B=Keta
	End If
	For i=0 To B
		if A(i)>Max then
			A(i+1)=A(i+1)+Fix(A(i)/Max)
			A(i)=A(i)-Fix(A(i)/Max)*Max
		End If
	Next i
End Sub

Sub Tasu(A As *Word,B As *Word,C As *Word)
	Dim i As Long
	for i=0 To Keta
		A(i)=B(i)+C(i)
	Next i
	Kuriagari_w(A)
End Sub

Sub Hiku(A As *Word,B As *Word,C As *Word)
	Dim i As Long
	Dim d(Keta) As Long
	For i=0 To Keta
		d(i)=B(i)-C(i)
	Next i
	For i=0 To Keta
		if d(i)<0 then
			d(i)=d(i)+Max
			d(i+1)=d(i+1)-1
			i=i-1
		End If
	Next i
	Ireru_l(A,d)
End Sub

Sub Kakeru(A As *Word,B As *Word,C As Word)
	Dim i As Long
	Dim d(Keta) As DWord
	For i=0 To Keta
		d(i)=B(i)*C
	Next i
	Kuriagari_dw(d)
	Ireru_dw(A,d)
End Sub

Sub Kakeru_t(A As *Word,B As *Word,C As *Word)
	Dim i As Long
	Dim j As Long
	Dim d(Keta*2+1) As DWord
	For i=0 To Keta
		For j=0 To Keta
			d(i+j)=B(i)*C(j)
		Next j
		Kuriagari_dw(d,Keta*2+1)
	Next i
	Ireru_dw(A,d)
End Sub

Sub Waru(A As *Word,B As *Word,C As Word)
	Dim i As Long
	Dim d(Keta) As Word
	Dim e(Keta) As Word
	Ireru(e,B)
	For i=Keta To 1 Step -1
		A(i)=Fix(e(i)/C)
		d(i)=e(i)-A(i)*C
		e(i-1)=e(i-1)+d(i)*Max
	Next i
	A(0)=Fix(e(i)/C)
End Sub

Sub Waru_t(A As *Word,B As *Word,C As *Word)
	Dim i As Long
	Dim j As Long
	Dim k As Long
	Dim d(Keta) As Word
	Syokika(A,0)
	For i=Keta To 0 Step -1
		if C(i)<>0 then
			Exit For
		End If
	Next i
	i=Keta-i
	j=100
	A(i)=j
	Do
		Kakeru_t(d,A,C)
		Hikaku(d,B,k)
		if k=1 then
			A(i)=A(i)-j
			j=j/10 As Long
			if j<1 then
				i=i-1
				j=1000
			End If
		Elseif K=0 then
			Exit Do
		Elseif K=-1 then
			A(i)=A(i)+j
		End If
		if i<0 then
			Exit Do
		End If
	Loop
End Sub

Sub Rujo(A As *Word,B As *Word,C As Word)
	Dim i As Long
	Dim d(Keta) As Word
	Syokika(A,0)
	if C=0 then
		A(0)=1
		Exit Sub
	Elseif C=1 then
		Ireru(A,B)
		Exit Sub
	End If
	Ireru(A,B)
	For i=2 To C
		Kakeru_t(d,A,B)
		Ireru(A,d)
	Next i
End Sub

Sub WriteToFile_t(FileName As BytePtr,A As *Word)
	Dim i As Long
	Dim j As Long
	Dim a$ As String
	For i=Keta To 0 Step -1
		if A(i)<>0 then
			Exit For
		End If
	Next i
	a$=Str$(A(i))
	j=0
	i=i-1
	Open FileName For Output As #1
	Do
		a$=a$+Str2$(A(i))
		i=i-1
		if i=-1 then Exit Do
		j=j+1
		if j=25 then
			Print #1,a$
			a$=""
			j=0
		End If
	Loop
	if a$<>"" then
		Print #1,a$
	End If
	Close #1
End Sub

Function Str2$(A As Word) As String
	Dim a$ As String
	a$=Str$(A)
	Select Case Len(a$)
		Case 1
			a$="000"+a$
		Case 2
			a$="00"+a$
		Case 3
			a$="0"+a$
	End Select
	Str2$=a$
End Function

Const Max=10000
Const Keta=2500

'差分そのいち

Sub Print_t(A As *Word)
	Dim i As Long
	Dim j As Long
	Dim a$ As String
	For i=Keta To 0 Step -1 
		if A(i)<>0 then 
			Exit For 
		End If 
	Next i 
	if i=-1 then
		Print "0"
		Exit Sub
	End If
	a$=Str$(A(i)) 
	j=0 
	i=i-1
	Do 
		a$=a$+Str2$(A(i)) 
		i=i-1 
		if i=-1 then Exit Do 
		j=j+1 
		if j=20 then 
			Print a$ 
			a$="" 
			j=0 
		End If 
	Loop
	if a$<>"" then Print a$
End Sub


'差分そのに
Sub Mod_t(A As *Word,B As *Word,C As *Word)
	Dim i As Long
	Dim d(Keta) As Word
	Dim e(Keta) As Word
	Waru_t(d,B,C)
	Kakeru_t(e,d,C)
	Hiku(A,B,e)
End Sub

'差分そのさん
Sub Val_t(A As *Word,A$ As String)
    Dim i As Long
    Dim a$ As String
    Dim b$ As String
    a$=A$
    i=0
    while Len(a$)>4
        b$=Mid$(a$,Len(a$)-3,4)
        A(i)=Val(b$)
        i=i+1
        a$=Left$(a$,Len(a$)-4)
    Wend
    if a$<>"" then
        A(i)=Val(a$)
    End If
End Sub

Sub Input_t(A As *Word)
    Dim a$ As String
    Input a$
    Val_t(A,a$)
End Sub

sbpファイルに分けることを推奨。

[konisi]

多倍長計算な変数（以下「多倍数」、対義語を「普通数」という。）は次のように定義してください。

Dim *(Keta) As Word

*の部分は好きな変数名

主な各関数の使用方法

■Syokika(A As *Word,B As Word)(C As Long)

Aに初期化する多倍数を入れてください。
Bに多倍数を初期化する値を入れてください。通常は0です。
Cは普通使いません。配列の数が定数Ketaと異なる場合に配列数を指定します。

例:
Dim A(Keta) As Word
Syokika(A,0)

■Ireru(A As *Word,B As *Word)

Aに代入先の多倍数を入れてください。
Bに代入元の多倍数を入れてください。

具体的な操作:A=B

■Hikaku(A As *Word,B As *Word,ByRef K As Long)(ByRef L As Long)

AとBに比較したい多倍数を入れてください。
Kに比較結果を返します。Lには「最上桁から数えて何桁目まであっていたか」というおまけ情報が返ってきます。

A>Bの時　K=1
A=Bの時　K=0
A<Bの時　K=-1

■Tasu(A As *Word,B As *Word,C As *Word)

Aに計算結果を返す為の多倍数を入れてください。
Bには足される数の入っている多倍数を入れてください。
Cには足す数の入っている多倍数を入れてください。

具体的な操作:A=B+C

■Hiku(A As *Word,B As *Word,C As *Word)

Aに計算結果を返す為の多倍数を入れてください。
Bには引かれる数の入っている多倍数を入れてください。
Cには引く数の入っている多倍数を入れてください。

具体的な操作:A=B-C

■Kakeru(A As *Word,B As *Word,C As Word)

Aに計算結果を返す為の多倍数を入れてください。
Bには掛けられる数の入っている多倍数を入れてください。
Cには掛ける数の普通数を入れてください。

具体的な操作:A=B*C

注意:この関数では多倍数同士の掛け算は行えません。
多倍数同士の掛け算にはKakeru_t関数を用いてください。

■Kakeru_t(A As *Word,B As *Word,C As *Word)

Aに計算結果を返す為の多倍数を入れてください。
Bには掛けられる数の入っている多倍数を入れてください。
Cには掛ける数の入っている多倍数を入れてください。

具体的な操作:A=B*C

■Waru(A As *Word,B As *Word,C As Word)

Aに計算結果を返すための多倍数を入れてください。
Bには割られる数の入っている多倍数を入れてください。
Cには割る数の普通数を入れてください。

具体的な操作:A=B/C

注意:この関数では多倍数同士の割り算は行えません。
多倍数同士の割り算にはWaru_t関数を用いてください。

■Waru_t(A As *Word,B As *Word,C As *Word)

Aに計算結果を返すための多倍数を入れてください。
Bには割られる数の入っている多倍数を入れてください。
Cには割る数の入っている多倍数を入れてください。

具体的な操作:A=B/C

注意:この関数では多倍数同士の割り算は行えません。
多倍数同士の割り算にはWaru_t関数を用いてください。

■Ruijo(A As *Word,B As *Word,C As Word)

Aに計算結果を返すための多倍数を入れてください。
Bに累乗の低となる数の入っている多倍数を入れてください。
Cに累乗の回数の普通数を入れてください。

具体的な操作:A=B^C

■WriteToFile_t(FileName As BytePtr,A As *Word)

FileNameに出力先のファイル名をポインタ参照で渡してください。
Aに出力する多倍数を入れてください。

具体的な操作:A配列を書き出し用の表示形式にしてファイルに出力




尚、使える桁数を増やしたい時はKetaの数値を高くしてみてください。

[TTP]

そのプログラムをperfect.sbpとして保存した後、このようにプログラムを
書いてみましたが、デバッグの段階でこのように怒られます。

スレッド(&H624)でアクセス違反がありました(EPI=&H00402F81)。

恐らくこちらのプログラムに問題があるのでしょうが、いまいちよくわかりません。

コード: 全て選択

#console
#include "perfect.sbp"

Dim BB As Word
Dim CC As Word
Dim ABC(Keta) As Word
Syokika(ABC,0)

BB="1000000000000000000"
CC="1000000000000000000000000"

Tasu(ABC,BB,CC)
Print ABC

[konisi]

数値に直接代入することは出来ません。
0番目の配列から順に4桁に区切って代入してください。
ついでに、表示用の関数を追加しておきます。

コード: 全て選択

'差分
Sub Print_t(A As *Word)
    Dim i As Long
    Dim j As Long
    Dim a$ As String
    For i=Keta To 0 Step -1 
        if A(i)<>0 then 
            Exit For 
        End If 
    Next i 
    a$=Str$(A(i)) 
    j=0 
    i=i-1
    Do 
        a$=a$+Str2$(A(i)) 
        i=i-1 
        if i=-1 then Exit Do 
        j=j+1 
        if j=25 then 
            Print a$ 
            a$="" 
            j=0 
        End If 
    Loop
    if a$<>"" then Print a$
End Sub

使い方
■Print_t(A As *Word)
Aに表示する多倍数を入れてください。
備考:#N88BASIC,#prompt,#consoleのどれかを有効にしてから使ってください。

コード: 全て選択

#console 
#include "perfect.sbp"

Dim BB(Keta) As Word
Dim CC(Keta) As Word
Dim ABC(Keta) As Word

BB(0)=0
BB(1)=0
BB(2)=0
BB(3)=0
BB(4)=100

CC(0)=0
CC(1)=0
CC(2)=0
CC(3)=0
CC(4)=0
CC(5)=0
CC(6)=1

Tasu(ABC,BB,CC)
Print_t(ABC)

修正するべき関数が見つかったので、関数を直しておいてください。(3つ上の関数群の方は既に書き直しました。）
WriteToFile_t関数、Kakeru関数

コード: 全て選択

Sub WriteToFile_t(FileName As BytePtr,A As *Word) 
    Dim i As Long 
    Dim j As Long 
    Dim a$ As String 
    For i=Keta To 0 Step -1 
        if A(i)<>0 then 
            Exit For 
        End If 
    Next i 
    a$=Str$(A(i)) 
    j=0 
    i=i-1 
    Open FileName For Output As #1 
    Do 
        a$=a$+Str2$(A(i)) 
        i=i-1 
        if i=-1 then Exit Do 
        j=j+1 
        if j=25 then 
            Print #1,a$ 
            a$="" 
            j=0 
        End If 
    Loop 
    if a$<>"" then 
        Print #1,a$ 
    End If 
    Close #1 
End Sub 

Sub Kakeru(A As *Word,B As *Word,C As Word)
	Dim i As Long
	Dim d(Keta) As DWord
	For i=0 To Keta
		d(i)=B(i)*C
	Next i
	Kuriagari_dw(d)
	Ireru_dw(A,d)
End Sub

[konisi]

関数をもういっこ追加っと。

コード: 全て選択

Sub Mod_t(A As *Word,B As *Word,C As *Word)
	Dim i As Long
	Dim d(Keta) As Word
	Dim e(Keta) As Word
	Waru_t(d,B,C)
	Kakeru_t(e,d,C)
	Hiku(A,B,e)
End Sub

使用方法
■Mod_t(A As *Word,B As *Word,C As *Word)
Aに計算結果を返す為の多倍数を入れてください。
Bに割られる多倍数を入れてください。
Cに割る多倍数を入れてください。

具体的な操作:A=B Mod C

備考:割り算の余りを計算します。

[TTP]

ありがとうございました！
使えるようになりました。

しかし、コンパイルの時に、「perfect.sbp(262) - 文法が間違っています」
と出ます。（今はコメントアウトで対応してます）
ちなみに、その262行目には、
Sub Mod(A As *Word,B As *Word,C As *Word)
とあります。

[konisi]

関数名が既存のものとダブってしまったみたいですね。

関数名をMod_tに変更してください。