باقیمانده تقسیم در سی++

[hafez1]

سلام دوستان.
من یک برنامه ای نوشتم که در اون نیاز دارم از یک عدد 96 بیتی نسبت به عدد 96 مد بگیرم.
حالا من این عدد 96 بیتی رو در قالب یک متغیر bitset در نظر گرفتم. و تابع مد رو خودم به این صورت تعریف کردم که تا جایی که عدد اول(عدد 96 بیتی) را از 96 کم میکنم و حاصل تفریقشون رو داخل یه متغیر میریزم و از این به بعد این متغیر به جای عدد اولم از 96 کم میشه تا جایی این دو عدد رو از هم کم میکنم که حاصل تفریق از 96 کمتر بشه و این میشه باقیمانده تقسیم.
ولی این خیلی طولانیه و هرچی هم صبر میکنم جوابی برنمیگردونه.
شما روش سریعتری ندارید؟

[ali chegini]

سلام.
راه هایی که فکر کنم بهت کمک میکنه :
1- یه پیشرفت کار برای برنامت بزار (progress bar)
2- اگر A/B = C ، صورت خیلی بزرگ باشه و مخرج کوچک حلقه ی که گذاشتی خیلی باید تکرار بشه. با توجه به اینکه باقیمانده تقسیم
از روش زیر به دست میاد :

mod= A-(C*B)

اگر ما بتونیم صورت رو به روشی کوچک تر کنیم یا مخرج رو به روشی بزرگتر کنیم . تکرار حلقه ها برای منها کردن کمتر میشه
برای بزرگ تر کردن از ضریب K می تونیم استفاده کنیم.

A*K/B*K = K*(A/B*K) = K*R=C


mod= A-(K*R*B)

حالا دوتا عدد بزرگ از هم کم میشه ولی این راه خطا داره . باید برای محاسبه ی خطا هم فکری کنی.
مثال :
خطا رو می تونی ببینی

A=1001
B=2
K=500

1001*500/2*500 = 500 ( 1001/2*500) = 500 * 1.001
mod = 1001 - ( 500 * 1.001 * 2 ) = 0
mod = 1001 - ( 500 * 1.00 * 2 ) = 1

[a.r.khoshghalb]

سلام.
فرض کنید عدد شما A هست.
میخواید A مود 96 رو حساب کنید.
خوب فرض کنید جواب بشه B. یعنی:

A % 96 = B

این یعنی یه عددی مثل C هست که :

C * 96 + B = A
و

(C+1) * 96 > A

خوب حالا اگر ما بتونیم سریع این C رو بدست بیاریم حله دیگه. ضربدر 96 می کنیمش و از A کمش میکنیم.
باینری سرچ میزنیم. یعنی اول فرض میکنیم C بین 2 عدد Min و Max باشه.
بعد نگاه میکنیم که اگر C برابر Min+Max تقسیم بر 2 (یعنی وسط بازه Min-Max) باشه C ضربدر 96 از A بزرگتر میشه یا کوچیکتر. اگر بزرگتر شد پس C مون باید کوچیکتر شه پس Max رو برابر Min+Max تقسیم بر 2 (یعنی وسط بازه Min-Max) قرار میدیم و دوباره الگوریتم رو اجرا میکنیم. اگر کوچیکتر شد پس C مون باید بزرگتر بشه پس Min رو برابر Min+Max تقسیم بر 2 (یعنی وسط بازه Min-Max) قرار میدیم و از اول انجام میدیم الگوریتم رو. اگر باینری سرچ بلدید یا با توضیحات مختصر من متوجه شدید که هیچ وگرنه پیشنهاد میکنم تو اینترنت سرچ کنید تا یاد بگیرید.
حالا این بازه (Min, Max) هر چه قدر هم که بزرگ باشه موردی نداره چون باینری سرچ در زمان log طول بازه * زمانی که برای چک کردن اینکه این جواب، جواب خوبی هست یا نه کار میکنه.
یعنی اگر Min تون 0 و Max تون 100^2 باشه به شرط اینکه به روش خوبی چک کنید که آیا این جواب درست هست یا نه زیر نیم ثانیه جواب میده.

ولی یه موردی وجود داره. اینکه تو این مساله C میتونه خیلی بزرگ بشه. انقدر:

((2^97) - 1) / 96

و خوب تو هیچ متغیری جا نمیشه این مقدار. باید فکر کنید به اینکه چطور چک کنید جوابتونو که خیلی کند نشه. احتمالا هر روشی به ذهنتون برسه زمانش خوب باشه، چون برای چک میتونید 6^10 عملیات انجام بدید (اگر بخواید زیر یک ثانیه جواب بگیرید)

ولی شاید اگر بگید دقیقا میخواید چکار کنید و از نتیجه این برنامه میخواید چه استفاده ای بکنید بتونیم کمکتون کنیم که بهینه تر بسازید برنامتونو. گاهی اوقات میبینید اصلا نیازی به نوشتن برنامه برای بعضی کارها نیست و میشه اون ها رو به روش های راحت تری حل کرد.

[Ananas]

سلام.
به شکل باینری تقسیم رو انجام بدید فقط کافیه یک حلقه ی حداکثر 96 تایی به ازای هر بیت طی کنید. در یک چشم به هم زدن جواب رو بدست میاره. خیییییلیییییی سریع تر از روشی که گفتید.

int Int64_Log2(const __int64 i)
{
int result = 63;
while ((i & (1UI64 << result)) == 0UI64)
result--;
return result;
};

__int64 Divide(
const __int64 i1,
const __int64 i2,
__int64 * p_remainder = NULL)
{
#define _0_ 0I64
#define _1_ 1I64
__int64 ui64, ui64Sub, Maqsum, MaqsumElaih;
int i;

if (i2 == _0_)
{
//ShowMessage('Error');
return 0xffffffffffffffffUI64;
};
if ( i1 == _0_ )
{
return _0_ ;
};

ui64 = _0_ ;
Maqsum = abs(i1);
MaqsumElaih = abs(i2);


i = Int64_Log2(Maqsum) - Int64_Log2(MaqsumElaih);
while ( i >= 0 )
{
ui64Sub = Maqsum - (MaqsumElaih << i);
if ( ui64Sub >= _0_ )
{
ui64 |= (_1_ << i);
Maqsum = ui64Sub;
};
i--;
};

if (p_remainder != NULL)
p_remainder[0] = Maqsum;

if (( i1 < _0_ ) != ( i2 < _0_ ))
return -ui64;
else
return ui64;
};

این یک مثال برای یک عدد 64 بیتی هست که جمع و تفریق و شیفت رو لازم نیست تابعی براش تعریف کنیم. البته تقسیم دو عدد 64 بیتی اصلا کلا نیازی به این تابع نداره کافیه از / استفاده کنیم:چشمک: ولی من برای تست روشم این کارو انجام دادم.
به حلقه ی داخل تابع دقت کنید. قسمت مهمش همونجاست. تابع Int64_Log2 تعریف کردم تا اولین بیتی که 1 هست از سمت چپ برام پیدا کنه. (یعنی تعداد ارقام عدد تو سیستم دودویی، منهای یک).
وقتی مقسوم علیه رو شیفت میدیم به سمت چپ به تعداد n تا، به این معنی هست که بیت n ام ضربدر مقسوم علیه. یادتونه تو ضرب ده دهی هر چی رقما اضافه میشد یک صفر اضافه میکردیم تو خط بعدی. اینجا همون شیفته. برای اینکه چک کنیم که اگر بیت n ام جواب، یک باشه و ضرب بشه تو مقسوم علیه، از مقسوم بزرگتر میشه یا نه. برای اینکه هر بار ضرب نکنیم کافیه مقدار اضافی هر مرحله رو کم کنیم.
برای 96 بیتی هم به همین روش میتونید عمل کنید با همون بیت ست فقط تابع تفریق لازم دارید که تعریف کنید.