掛け算、割り算を加減算だけで実装したい

[KEYONN_]

こんにちは、TKOZです。

今、ファミコンのアセンブラにはまっているのですが、
ファミコンは８ビットＣＰＵで掛け算と割り算の命令がありません。

そこで、まずは、Ｃ言語だけでアルゴリズムを考えようとしたのですが、
なかなか上手くいきませんでした。

上手くいかないのは、int型で小数を扱うには、どうすればいいかという事が分かりません。
とりあえず、１００倍して、答えを１００で割るという手段を用いているのですが、
ファミコンのアセンブラに移植した場合、
例えば１７０.５２という値だと（まあ、こんな値は普段使いませんが…）、１７０５２という値に
なりオーバーフローしてしまいます。どうすればいいでしょうか？何か良い案があればお願いします。

ファミコンのアセンブラの開発環境はnesasmで、Ｃ言語の開発環境は、BCCDeveloperとVC++6.0です。
WindowsXPです。

ソースは以下の通りです。

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

int mul(int a,int b)
{
    int sum=0;
    for(int i=0;i<b;i++)
        sum+=a;
    return sum;
}

int div01(int a,int b)
{
    int sum=a;
    int count=0;
    while((sum-=b)>=0)
    {
        count++;
    }
    return count;
}

typedef struct Div{
    int num1;
    int num2;
}Div;

int main()
{
    int i,j;
    float k,l;
    Div D[81]={ {1,1},{2,1},{3,1},{4,1},{5,1},{6,1},{7,1},{8,1},{9,1},
            {2,2},{4,2},{6,2},{8,2},{10,2},{12,2},{14,2},{16,2},{18,2},
            {3,3},{6,3},{9,3},{12,3},{15,3},{18,3},{21,3},{24,3},{27,3},
            {4,4},{8,4},{12,4},{16,4},{20,4},{24,4},{28,4},{32,4},{36,4},
            {5,5},{10,5},{15,5},{20,5},{25,5},{30,5},{35,5},{40,5},{45,5},
            {6,6},{12,6},{18,6},{24,6},{30,6},{36,6},{42,6},{48,6},{54,6},
            {7,7},{14,7},{21,7},{28,7},{35,7},{42,7},{49,7},{56,7},{63,7},
            {8,8},{16,8},{24,8},{32,8},{40,8},{48,8},{56,8},{64,8},{72,8},
            {9,9},{18,9},{27,9},{36,9},{45,9},{54,9},{63,9},{72,9},{81,9}
        };
    
    srand(time(NULL));
    
    for(i=1;i<=9;i++)
    for(j=1;j<=9;j++)
    printf("%d×%dは%dです。:",i,j,mul(i,j));
    
    for(k=0.0;k<=1.0;k+=0.1)
    {
        for(l=0.0;l<=1.0;l+=0.1)
        {
            printf("%.4f×%.4fは%.4fです。:",k,l,mul(k*100,l*100)/100.0/100.0);
        }
    }
    
    for(i=1;i<=9;i++)
    {
        for(j=1;j<=9;j++)
        {
            int n1=rand()%81;
            printf("%d÷%dは%dです。:",
            D[n1].num1,D[n1].num2,div01(D[n1].num1,D[n1].num2));
        }
    }
    
    for(k=1;k<=9;k+=1)
    {
        for(l=1;l<=9;l+=1)
        {
            float a=rand()%10/10.0;
            float b=rand()%10/10.0;
            printf("%.4f÷%.4fは%dです。:",a,b,div01(a*100,b*100));
        }
    }
    
    return 0;
}

[softya]

ファミコンだと出来れば１６ビットで表現できる範囲で計算したほうが良いと思います。
１６ビットの値の範囲は符号付きで-32768～32767となります。
で、ファミコンで座標系は横２５６ドット程度でしょうから、32768/256=128=(2の７乗)分を小数点にまわせる計算になります。ここまでＯＫでしょうか？

bitイメージとしては、こんな感じです。
□□□□□□□□□□□□□□□□
s 8 7 6 5 4 3 2 1 0 -1-2-3-4-5-6
sは符号。数字は２の乗数で、-1～-6は小数点以下の数値部分です。
この考え方をfloatの浮動小数点の対語として固定小数点と呼びます。

こうするメリットは２進数基本で考える事で、掛け算や割り算を使わずにシフト演算だけで少数化が出来ることにあります。
たとえば、7を小数点つきにする場合。
short speed;
speed = 7 << 7; //これで7.0って意味なります。
//で、速度を半分にする場合は、
speed = speed >> 1;　//これで3.5って意味になります。
//これでＸ座標を計算してみましょう。
short x = 128 << 7;
x += speed; //128+3.5の計算となります。
printf( "x=%d\n", x >> 7 );//これで小数点以下を切り捨てたＸ座標を取り出せます。

効率的な掛け算と割り算に付いては、別に説明しますね。

[Justy]

＞どうすればいいでしょうか？

　ファミコンはたしか PCレジスタ以外は 8ビットでしたっけ？
　
　なら、C的に言えば unsigned char [2]で擬似的に 16bit計算をするライブラリを
作ってはどうでしょうか。

　今時の int型にしたいなら、unsigned char [4]で。

　つまり、多倍長整数ですね。

[KEYONN_]

＞softyaさん
＞Justyさん

ファミコンで大きな桁の値を表す時は、多倍長演算を使うんですね。

＞ファミコンはたしか PCレジスタ以外は 8ビットでしたっけ？
はい、そうです。

＞なら、C的に言えば unsigned char [2]で擬似的に 16bit計算をするライブラリを
＞作ってはどうでしょうか。
ちょっと、やってみます。
ただ、分からない事があれば、質問するか、自分で調べてみます。

とりあえず、四則演算は完璧にしたいですね。それから、比較、出力を実装したいです。

[Justy]

＞ファミコンで大きな桁の値を表す時は、多倍長演算を使うんですね

　もう少し限定的なら個別に大きな値を扱う方法があるかもしれませんが、
汎用的に、しかも固定少数での利用となると、これくらいしか思いつかないです。

　でも、経験者なら何か別のアイデアがあるかもしれません。

[softya]

Ｚ８０系の人なんで６５０２に詳しくないですが、とりあえず８ビットＣＰＵで１６ビット演算する方法です。
まず簡単な、６５０２の１６ビット加減算
http://sldnoonmoon.hp.infoseek.co.jp/ne ... c/d_4.html
８ビットマイコンは、キャリーフラグの活用がキモとなります。、

特に掛け算割り算は、シフト、ローテイトを駆使しないと高速な演算は出来ません。
ややっこしくなるので、１６ビットの加減算が理解できるようなら説明しますけど。

[たかぎ]

RP2A03とも6502とも違うので完全互換とはいきませんが...

http://documentation.renesas.com/jpn/pr ... _740ap.pdf

↑を参考にすると役に立つ可能性大です。
ただ、RP2A03（あるいは6502）では、Z80なんかに比べても16ビットの演算は非常にやりにくいので、8ビットで済むところは済ます、16ビットが必要でも16ビット×8ビットにする、割り算や小数は極力使わないなどの工夫が必要です。

実機の場合には、MMCやROMのサイズによっては表引きもできなくはないですが、普通は現実的ではないでしょう。
一方でエミュレータの場合は、エミュレータ自身を拡張すれば、ハードウェアの非力さを補うこともできるのではないでしょうか？

[KEYONN_]

＞＞たかぎさん
＞＞softyaさん
＞＞Justyさん

数日間、悩んでいましたが、いい情報を得られたので、
解決とさせていただきます。