足し算と引き算だけでつくる演算

半分数学の問題なのですが、考え方はプログラミングなのでこちらのカテゴリで質問しました。

大学で計算の可能性という講義を受けています。
この講義ではwhileプログラムというプログラムを使って計算の可能性を調べる講義です。
そこで

足し算、引き算のみを用いて割り算、剰余、指数、対数を計算する手続きを作れという問題が出されました。

割り算、剰余は

procedure z = x div y:
begin u1 := x; u2 := y; z := 0;
while u1 >= u2 do
begin u1 := u1 - u2;
z := z + 1;
end
end

procedure z = x mod y:
begin u1 := x; u2 := y; z := 0;
while u1 >= u2 do
begin u1 := u1 - u2;
z := u1;
end
end

という手続きでできそうだとわかりました。
（Ｃ言語で似たような関数をつくり確認しました。）
しかし、指数と対数を求める手続き
procedure z := x ** y:
と
procedure z := log2 x:
がどうすればよいか分かりません。
この２つを教えていただけないでしょうか？
プログラムの流れが分かればいいので足し算引き算のみ使用しているならＣ言語でもいいです！
よろしくお願いします。

No.3 ベストアンサー 回答者： tatsu99 回答日時： 2008/01/19 22:35

C言語で作成しました。

動作確認済みです。
----------------------------------------
#include <stdio.h>
#include <stdlib.h>
// x,yは自然数である。従ってx>0,y>の整数とする。
//[while]に敬意を表し、for文でなく、while文で
//プログラムを作成する

// x*yの結果を返す関数
// これは、powerから呼ばれる補助関数
int multiply(int x,int y)
{
int i = 1;
int ans = x;
//xをy回たせば、掛け算になる
while(i < y){
ans = ans + x;
i++;
}
return ans;
}
// x**yの結果を返す関数
int power(int x,int y)
{
//x*xをy回繰り返す。
int ans = x;
int i = 1;
//x*xをy回繰り返すと、x**yになる
while(i < y){
ans = multiply(ans,x);
i++;
}
return ans;
}
// x/yを返す関数
// これは、log2から呼ばれる補助関数
int divide(int x,int y)
{
int ans = 0;
//xからy回引き算すると割り算になる
while(x >= y){
x = x - y;
ans++;
}
return ans;
}
// log2 x を返す関数 (2を底とするxの対数)
int log2(int x)
{
int ans = 0;
//xを2で１になるまで割る。（1より大きい間実行）
//その回数が求める解
while (x > 1){
ans++;
// y/2を求める
x = divide(x,2);
}
return ans;
}
int main(int argc , char **argv)
{
int ans;
ans = power(2,4);
printf("2**4=%d\n",ans);
ans = log2(16);
printf("log2 16=%d\n",ans);
}

No.4 回答者： Tacosan 回答日時： 2008/01/19 23:27

#2 の補足のところに対してですが, 「計算の可能性」という表現からすると, おそらく while プログラムは「計算のモデル」として使っているんじゃないかなぁという気がします. そういう意味では, まさに「数学で使うことを目的にしている」といっていいかと思います.

計算モデルとしては Turing機械がもっとも一般的に使われていると思いますが, 正直いって「実際に使うととっても面倒」なので, より記述しやすい (かつ等価な) モデルを使うこともあります. こちらだと普通は RAM (Random Access Machine) のような気がしますが, while プログラムでもほぼ同じです.

No.2 回答者： tatsu99 回答日時： 2008/01/19 21:11

x,yは正の整数という前提でよいのですか。

負の値も含みますか。
実数も含みますか。
その前提がわかると、良い回答が得られるかと思います。

この回答への補足

教科書によると、whileプログラムは自然数のみを扱うようです。
whileプログラムというプログラム自体自分も聞いたことが無く、今受けている講義で初めて知りました。
おそらく実用的なＣ等とは違い、数学で使うことを目的に作られたもののようですね。

補足日時：2008/01/19 21:13

No.1 回答者： himajin100000 回答日時： 2008/01/19 18:50

うーん。

自信ない。現状x,y,zが整数になっているけど，
それ以外のケースってどうやったらいいんだろう・・・

とりあえず整数だけに限る。

ある関数に含まれる全ての関数が加算・減算のみで出来ているなら
その関数は加算・減算のみで出来る、よね？多分・・・・A
======================================
一気に累乗を考えると混乱するので，

累乗を掛け算で示す。

x**y = x * x * x *・・・
ってのをy回繰り返したものだよね？

x * yってどうやるかって言ったら(yが整数なら)
xをy回足せばいい。
C#が自分は慣れているのでC#で書くなら
multiple(x,y) = x * yは以下のように書く。

namespace Q3694102
{
class Program
{
public static void Main(string[] args)
{
System.Console.WriteLine(multiple(2,3).ToString()); /* 表示するだけ */
System.Console.ReadKey(true);　/* キーを押すまで待機　*/
}
public static int multiple(int x,int y)
{
int z = 0;
for (int i=y;i>0;i--){
z = z + x;
}
return z;

}
}

となる。
==========================================================
pow関数は

namespace Q3694102
{
class Program
{
public static void Main(string[] args)
{
System.Console.WriteLine(pow(2,3).ToString()); /* 表示するだけ */
System.Console.ReadKey(true);　/* キーを押すまで待機　*/
}

public static int pow(int x,int y){
int z = 1;
for(int i = y;i>0;i--){
z = multiple(z,x);
}
}

public static int multiple(int x,int y)
{
int z = 0;
for (int i=y;i>0;i--){
z = z + x;
}
return z;

}


}

となるだろう。
====================
Aがあるので，後は展開するだけ。
変数のスコープが違うから同じ名前の変数が混在していたが，
一つに纏めるとなったら呼び出し元の同名変数を書き換えないように，
仮引数用の変数に書き換える

namespace Q3694102
{
class Program
{
public static void Main(string[] args)
{
System.Console.WriteLine(pow(2,3).ToString()); /* 表示するだけ */
System.Console.ReadKey(true);　/* キーを押すまで待機　*/
}

public static int pow(int x,int y){
int z = 1;
for(int i = y;i>0;i--){
//multiple関数の展開，ここから

int m = 0;
for (int j = x;j>0;j--){
m = m + z;
}
z = m;


}
return z;
}
}

}
===============================
次，対数。
z := log2 x:
要するに，
2**z = x;
となるような整数zをループ回して探せ、と。

namespace Q3694102
{
class Program
{
public static void Main(string[] args)
{
System.Console.WriteLine(log(2,3).ToString()); /* 表示するだけ */
System.Console.ReadKey(true);　/* キーを押すまで待機　*/
}

public static int pow(int x,int y){
int z = 1;
for(int i = y;i>0;i--){
//multiple関数の展開，ここから

int m = 0;
for (int j = x;j>0;j--){
m = m + z;
}
z = m;


}
return z;
}
public static int log(int x,int y){
int z = 0;
int i = 1;
while(true){ /* 本当はオーバーフローとか気にしないといけない。*/
if (pow(x,i) > y){
break;
}
z = z + 1;
i = i + 1;
}
return i - 1;
}
}

}

後はこれを展開するだけ。面倒くさいけど。

==================================
x,yが整数でなかったときの考察。
桁が許せば，になるけれど，
xとかyとかzがコンピュータであらわせる小数ってとき

x = a[0] * 2**(0) + a[1] * 2**(-1) + a[2] * 2**(-2)

とかになる。
上の例ならxに2**2掛ければ整数になるんじゃね？

zが整数でないとき。
うーん。
実数同士の掛け算・割り算が使えそうなら
2分法みたいので狭める手が使えるとは思うんだけど。
==================================
x,yが整数でなかったときの考察。
桁が許せば，になるけれど，
xとかyとかzがコンピュータであらわせる小数ってとき

x = a[0] * 2**(0) + a[1] * 2**(-1) + a[2] * 2**(-2)

とかになる。
上の例ならxに2**2掛ければ整数になるんじゃね？

zが整数でないとき。
うーん。
実数同士の掛け算・割り算が使えそうなら
2分法みたいので狭める手が使えるとは思うんだけど。

===========================
●x,yが負の時
●そもそもそんな解が存在しないとき。

log2(-1)とか

面倒くさいので考えてません。
============================