求一個除法的演算法 |
|
尚未結案
|
|
tokimeki
一般會員   發表：1 回覆：5 積分：1 註冊：2003-02-17 發送簡訊給我 |
|
|
無故障
一般會員 發表：17 回覆：69 積分：17 註冊：2004-03-11 發送簡訊給我 |
|
|
無故障
一般會員 發表：17 回覆：69 積分：17 註冊：2004-03-11 發送簡訊給我 |
|
|
tokimeki
一般會員 發表：1 回覆：5 積分：1 註冊：2003-02-17 發送簡訊給我 |
我後來有自己想到，但也不算是無限位數，
因為記錄"位數"的正整數，還是被限制在系統能直接加加減減的範圍內，
例如16位元的系統，最大也只能做65535位... 其實這個問題異常的簡單，我自己想到時也嚇了一跳，
那個其實就是模擬二進位除法，不過一個位元一個位元來處理，
跑的有點慢，其實可以改成一次處理32bits(因為目前我的電腦是IA32)。 不過目前還有個限制就是被除數要小於除數，這個其實也還好辦，
商和餘數分開處理就行，不過整個"數"的儲存方式可能跟你想的不太一樣就是。
不能直接拿來跟程式語言裡面宣告的"整數"或"浮點數"拿來運算。 底下的程式位了顯示方便所以用AnsiString來存資料，
實際上可以改成用Byte陣列來存，這樣才不會浪費空間
unsigned __int32 Dividend = DividendEdit->Text.ToIntDef(0);
unsigned __int32 Divisor = DivisorEdit->Text.ToIntDef(0);
unsigned __int32 _Dividend = Dividend;
unsigned __int32 _Divisor = Divisor;
unsigned __int32 Digit = DigitEdit->Text.ToIntDef(0);
unsigned __int32 Count = 0;
AnsiString Message;
AnsiString ErrMsg = "";
TStrings * Result = ResultMemo->Lines;
ResultMemo->Clear(); if (Dividend == 0 || Divisor == 0) {
ErrMsg = "被除數與除數須大於0\n";
} if (Digit < 1) {
ErrMsg = "計算位數須大於1\n";
} if (Dividend >= Divisor) {
ErrMsg = "被除數須小於除數\n";
} if (ErrMsg != "") {
ShowMessage(ErrMsg);
return;
} Message = AnsiString(Dividend) " / " AnsiString(Divisor) " = ";
Result->Append(Message); Result->Append("0.");
Message = "";
Dividend <<= 1; for( ; ; ) {
if (Dividend < Divisor) {
Message = "0";
} else {
Message = "1";
Dividend -= Divisor;
}
Dividend <<= 1;
Count ;
if (Count == Digit || Dividend == 0) {
Result->Append(Message);
break;
}
}
Result->Append(AnsiString("實際計算位數：") Count); double Oct = 0;
double OP = 1; for (unsigned __int16 i = 1; i <= Message.Length(); i ) {
OP /= 2;
if (Message[i] == '1') {
Oct = OP;
}
}
Result->Append(AnsiString("十進位浮點數：") Oct);
Oct = (double)_Dividend / _Divisor;
Result->Append(AnsiString("驗算後浮點數：") Oct); 發表人 - tokimeki 於 2004/04/22 23:57:10 發表人 - tokimeki 於 2004/04/22 23:59:17
|
|
jimmy_and_you
初階會員  發表：20 回覆：74 積分：33 註冊：2003-05-12 發送簡訊給我 |
引言: 題目是這樣的： 有兩個正整數i與j，其中i小於j，求i/j之數(當然這會是一個小數)， 且可給定一數k，表其小數點後的位數，k至少要大於65536(小數以二進位表示)。 我需要一個除法的演算法能做到上述的要求，並附上Big-O的時間複雜度分析... P.S.我搜尋過相關的文章，只找到能算到整數的無限位數算法，與我的需求不合，請各位幫幫忙，謝謝...我自己寫了一段Code可以求出32位元的除法(小數位數自己設定),輸出結果是2進位的,這程式有3個LOOP,我有注明各會跑幾次(有點忘了Big-O怎麼算)
// A / B = XXXX.YYYYYYYYYYYYYYYYYYYYYYYYYY
// |<---- C ---->|
void Div(const UINT32 A, const UINT32 B, UINT32 C)
{
UINT32 BitMask = 1;
UINT32 tA = A, tB = B;
UINT32 i;
if( B==0 )
{
printf("Error B = 0");
return;
}
//計算整數部分
if( A < B )
{
printf("0");
}
else
{
for( ; tA>=tB && !(tB&0x80000000); BitMask<<=1,tB<<=1 ) //-->最多32次
;
if( !((tB&0x80000000) && tA>=tB) )
{
BitMask>>=1;
tB>>=1;
}
for( ; BitMask!=0 ; BitMask>>=1,tB>>=1) //-->最多32次
{
if( tA>= tB )
{
tA-=tB;
printf("1");
}
else
printf("0");
}
}
//計算小數部分
if( tA != 0 )
{
printf(".");
for( i=0 ; i
|
|
tokimeki
一般會員 發表：1 回覆：5 積分：1 註冊：2003-02-17 發送簡訊給我 |
引言:您的程式我看過了，不過還算不上是無限位數， 不過比我之前寫的可以多處裡商的部份，無論如何，還是很感謝您。 我再等一個禮拜看看，若還是沒有人答題，我再把這個討論結案掉。引言: 題目是這樣的： 有兩個正整數i與j，其中i小於j，求i/j之數(當然這會是一個小數)， 且可給定一數k，表其小數點後的位數，k至少要大於65536(小數以二進位表示)。 我需要一個除法的演算法能做到上述的要求，並附上Big-O的時間複雜度分析... P.S.我搜尋過相關的文章，只找到能算到整數的無限位數算法，與我的需求不合，請各位幫幫忙，謝謝...我自己寫了一段Code可以求出32位元的除法(小數位數自己設定),輸出結果是2進位的,這程式有3個LOOP,我有注明各會跑幾次(有點忘了Big-O怎麼算) |
|
jimmy_and_you
初階會員 發表：20 回覆：74 積分：33 註冊：2003-05-12 發送簡訊給我 |
引言:如果要真正做到"完全"無限位數的除法,我只想到用字串做吧(您之前找到的整數無限除法,是否是這樣做?), 用字串做處理程式會複雜不少(若是2進位字串可能比較沒那麼複雜),還要撰寫相關字串加減法. 我之前POST的除法是我在單晶片用的做小修改. < >大家互相切磋求進步< >引言:您的程式我看過了，不過還算不上是無限位數， 不過比我之前寫的可以多處裡商的部份，無論如何，還是很感謝您。 我再等一個禮拜看看，若還是沒有人答題，我再把這個討論結案掉。引言: 題目是這樣的： 有兩個正整數i與j，其中i小於j，求i/j之數(當然這會是一個小數)， 且可給定一數k，表其小數點後的位數，k至少要大於65536(小數以二進位表示)。 我需要一個除法的演算法能做到上述的要求，並附上Big-O的時間複雜度分析... P.S.我搜尋過相關的文章，只找到能算到整數的無限位數算法，與我的需求不合，請各位幫幫忙，謝謝...我自己寫了一段Code可以求出32位元的除法(小數位數自己設定),輸出結果是2進位的,這程式有3個LOOP,我有注明各會跑幾次(有點忘了Big-O怎麼算) |
|
way99
一般會員 發表：10 回覆：10 積分：4 註冊：2003-06-16 發送簡訊給我 |
|
|
tokimeki
一般會員 發表：1 回覆：5 積分：1 註冊：2003-02-17 發送簡訊給我 |
我最近寫了一個BitList(一維)的容器，可以用來放二進位的小數...
Common.h
//--------------------------------------------------------------------------- #ifndef CommonH #define CommonH #includeBitList.h
//---------------------------------------------------------------------------
#ifndef BitListH
#define BitListH
#include "Common.h"
//---------------------------------------------------------------------------
enum TSizeUnit {
ByBit = 0,
ByNibble = 2,
ByByte = 3,
ByWord = 4,
ByDWord = 5,
ByQWord = 6
};
//---------------------------------------------------------------------------
enum TSizeMask {
NibbleMask = ~(MAX_UINT << ByNibble),
ByteMask = ~(MAX_UINT << ByByte),
WordMask = ~(MAX_UINT << ByWord),
DWordMask = ~(MAX_UINT << ByDWord),
QWordMask = ~(MAX_UINT << ByQWord)
};
//---------------------------------------------------------------------------
static const BYTE BitMask[] = {
0x80, 0x40, 0x20, 0x10,
0x08, 0x04, 0x02, 0x01
};
//---------------------------------------------------------------------------
class TBitList {
private:
UINT _Size;
BYTE * _Item;
BYTE * _StrBuf;
void __fastcall SetItemU(UINT X, BYTE Value);
BYTE __fastcall GetItemU(UINT X);
void __fastcall SetItemS(UINT X, BYTE Value);
BYTE __fastcall GetItemS(UINT X);
void Reset();
public:
BYTE OuterValue;
TBitList();
~TBitList();
void SetSize(UINT Size = 0);
void Free();
bool Empty();
UINT __fastcall Size(TSizeUnit SizeUnit = ByBit);
void SetAll(BYTE Value = 0);
bool InRange(UINT X);
const char * c_str();
__property BYTE ItemU[UINT X] = { read=GetItemU, write=SetItemU };
__property BYTE ItemS[UINT X] = { read=GetItemS, write=SetItemS };
__property BYTE * ItemPtr = { read=_Item };
};
//---------------------------------------------------------------------------
#endif
BitList.cpp
//---------------------------------------------------------------------------
#pragma hdrstop
#include "BitList.h"
#pragma package(smart_init)
//---------------------------------------------------------------------------
// 初始化函數
// Count : 位元數目
//---------------------------------------------------------------------------
void TBitList::SetSize(UINT Count)
{
Free();
_Size = Count;
_Item = new BYTE[Size(ByByte)];
}
//---------------------------------------------------------------------------
// 取得儲存位元的陣列大小
// SizeUnit : 長度單位 (預設值 : ByBit)
// ByBit : 以位元長度為單位 (1 Bit)
// ByByte : 以位元組長度為單位 (8 ItemS)
// ByWord : 以字組長度為單位 (16 ItemS)
// ByDWord : 以兩倍字組長度為單位 (32 ItemS)
// ByQWord : 以四倍字組長度為單位 (64 ItemS)
// 傳回值 : 以SizeUnit為單位的陣列大小
//---------------------------------------------------------------------------
UINT __fastcall TBitList::Size(TSizeUnit SizeUnit)
{
UINT Size = _Size >> SizeUnit;
UINT Mask = ~(MAX_UINT << SizeUnit);
if ((_Size & Mask) != 0) {
Size ;
}
return Size;
}
//---------------------------------------------------------------------------
// 測試位元陣列是否是空的
// 傳回值 : true -> 陣列是空的
// false -> 陣列不是空的
//---------------------------------------------------------------------------
bool TBitList::Empty()
{
if (_Size != 0) {
return true;
} else {
return false;
}
}
//---------------------------------------------------------------------------
// 設定所有陣列元素的值
// Value : 設定值 (預設值：0)
//---------------------------------------------------------------------------
void TBitList::SetAll(BYTE Value)
{
for (UINT i = 0; i < Size(ByByte); i ) {
_Item[i] = Value;
}
}
//---------------------------------------------------------------------------
// 釋放配置的陣列空間
//---------------------------------------------------------------------------
void TBitList::Free()
{
delete [] _Item;
delete [] _StrBuf;
Reset();
}
//---------------------------------------------------------------------------
// 解構函數
//---------------------------------------------------------------------------
TBitList::~TBitList()
{
Free();
}
//---------------------------------------------------------------------------
// 建構函數
//---------------------------------------------------------------------------
TBitList::TBitList()
{
OuterValue = 0;
Reset();
// Init(Count);
}
//---------------------------------------------------------------------------
// 設定指定的位元 (不檢查註標值)
// X : 第幾個位元 (從0開始算)
// Value : 欲設定的位元值
//---------------------------------------------------------------------------
void __fastcall TBitList::SetItemU(UINT X, BYTE Value)
{
if (Value != 0) {
_Item[X >> ByByte] |= BitMask[(X & ByteMask)]; // Set 1
} else {
_Item[X >> ByByte] &= ~BitMask[(X & ByteMask)]; // Set 0
}
}
//---------------------------------------------------------------------------
// 取得指定的位元值 (不檢查註標值)
// X : 第幾個位元 (從0開始算)
// 傳回值 : 取得的位元值
//---------------------------------------------------------------------------
BYTE __fastcall TBitList::GetItemU(UINT X)
{
if ((_Item[X >> ByByte] & BitMask[(X & ByteMask)]) == 0) {
return 0;
} else {
return 1;
}
}
//---------------------------------------------------------------------------
// 測試位元陣列的註標值是否在合法範圍內
// 傳回值 : true -> 註標值在合法範圍內
// false -> 註標值不在合法範圍內
//---------------------------------------------------------------------------
bool TBitList::InRange(UINT X)
{
if (X >= Size(ByBit)) {
return false;
} else {
return true;
}
}
//---------------------------------------------------------------------------
// 設定指定的位元 (會檢查註標值)
// 若註標值不在合法範圍內，什麼事都不做
// X : 第幾個位元 (從0開始算)
// Value : 欲設定的位元值
//---------------------------------------------------------------------------
void __fastcall TBitList::SetItemS(UINT X, BYTE Value)
{
if (InRange(X)) {
SetItemU(X, Value);
}
}
//---------------------------------------------------------------------------
// 取得指定的位元值 (會檢查註標值)
// 若註標值不在合法範圍內，則傳回OuterValue
// X : 第幾個位元 (從0開始算)
// 傳回值 : 取得的位元值
//---------------------------------------------------------------------------
BYTE __fastcall TBitList::GetItemS(UINT X)
{
if (InRange(X)) {
return GetItemU(X);
} else {
return OuterValue;
}
}
//---------------------------------------------------------------------------
// 取得位元陣列的內容，以字元陣列表示
// 傳回值 : 字元陣列的指標
//---------------------------------------------------------------------------
const char * TBitList::c_str()
{
delete [] _StrBuf;
_StrBuf = new char[_Size 1];
for (UINT i = 0; i < _Size; i ) {
if (GetItemU(i) == 0) {
_StrBuf[i] = '0';
} else {
_StrBuf[i] = '1';
}
}
_StrBuf[_Size] = 0;
return _StrBuf;
}
//---------------------------------------------------------------------------
void TBitList::Reset()
{
_Item = NULL;
_StrBuf = NULL;
_Size = 0;
}
//--------------------------------------------------------------------------- 發表人 - tokimeki 於 2004/05/26 20:55:12 發表人 - tokimeki 於 2004/05/26 20:56:14
|
|
tokimeki
一般會員 發表：1 回覆：5 積分：1 註冊：2003-02-17 發送簡訊給我 |
引言: 如果要真正做到"完全"無限位數的除法,我只想到用字串做吧(您之前找到的整數無限除法,是否是這樣做?), 用字串做處理程式會複雜不少(若是2進位字串可能比較沒那麼複雜),還要撰寫相關字串加減法. 我之前POST的除法是我在單晶片用的做小修改. < >大家互相切磋求進步< >我把最近寫的一個ButList容器貼出來，可以用這個代替字串，來放二進位值。 其實如果不計較計算位數的那個計數值，你跟我的方法都可以算是無限... 還沒看到其他人有超過這個範圍的解答，所以我把這個給結案掉... |
發表時間：2004-03-31 16:03:48
IP:163.17.xxx.xxx 未訂閱
系統時間：2024-05-12 21:48:25
聯絡我們 | Delphi K.Top討論版
| 本站聲明 |
|
1. 本論壇為無營利行為之開放平台，所有文章都是由網友自行張貼，如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權，而損及您的利益，請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨，是藍是綠本站無權干涉，但這裡不是政治性論壇！ |