محاسبه توان بدون استفاده از تکرار و بازگشت
همه ما روش پیدا کردن یک عدد به توان عدد دیگر رو بصورت تکراری (با حلقه) و بازگشتی
می دانیم ، ولی حالا روشی خیلی ساده تر و بهینه تر برای محاسبه توان :
کد برنامه :
#include <iostream>
#include <conio>
#include <math>
int main(){
int a,b;
cin>>a>>b;
cout<<exp(b*log(a));
getch();
}
موفق و پیروز باشید !!!
یه راه ساده تر و قاعده مند تر اینکه که از تابع pow استفاده کنی:
#include <iostream.h>
#include <math.h>
int main(){
int a,b;
cin>>a>>b;
cout<<pow(a,b);
}
هوالحکیم سلام خدمت دوستان عزیز جسارتاً عرض می کنم ولی ظاهراً منظور شما دوستان از کد های فوق، نوشتن a به توان b می باشد. خدمت دوست عزیز salar_cpp_cs عرض کنم که در این توابع از if و for و ... استفاده شده است! در ضمن از نظر تئوری مشکلی وجود ندارد ولی از نظر برنامه نویسی، برنامه شما برای a=0 با خطا مواجه می شود، ولی از ایده شما ممنونم. جالب است که بدانیم ماشین حساب رایانه و ... نیز از تابع شما استفاده می کنند چرا که با پیچیدگی ثابتی(مثلاً (2O(10) جواب می دهد ولی توان معمولی که ما می نویسیم به توان بستگی دارد و به تعداد عدد توان، تکرار در حلقه صورت می گیرد. به هر حال باز هم سپاسگزارم. یا علی. خدانگهدارتان
به نظر من براي اينكه پيچيدگي شو بدونيم بايد بدونيم كه هر كدوم از توابع چطور پياده سازي شده اند.
مثلا ممكنه كه خود اين توابع داخلشون تكرار داشته باشند و زمان بيشتري رو نسبت به روش خودمون بگيرند .
نظر شما چيه؟!
با تشكر.
الان كه به اين موضوع فكر مي كنم مي بينم كه حرف دوستانمون درسته و الگوريتمي كه در بالا ارائه شده داراي پيچيدگي ثابتي هست. چون تابع exp به صورت يك سري محاسبه مي شه و چه براي اعداد خيلي بزرگ وچه براي اعدادي مثل 1 اين سري تا بك حد مشخصي ادامه پيدا مي كنه.
پس هم براي اعداد بزرگ و هم براي اعداد كوچيك زمان يكساني رو مي گيره.
موفق باشيد.
من فقط میدونم که این روش log برای تواهای بالا کارآمده.مصارف اصلیش هم مثلاْ در احتمالات در مساپلی مثل روز تولد و یا در حسابداری برای محاسبه سوده:
Current=Initial*(1+P/100)^n
که n یک عدد خیلی خیلی بزرگه.
در نهایت همه محاسبات شما به 4 عمل اصلی ختم میشه، چون در معماری CPU ها عملگرها بسیار ساده هستند و مانند GPU ها توان محاسبه های همزمان رو ندارند، به این دلیل که کد های شما در نهایت در تعداد محدودی Adder و Multiplier به صورت ترتیبی محاسبه میشه، چون تعداد هسته ها بسیار کمه، یعنی در نهایت مثل همون For Loop میشه، تکرار یک عمل پشت سر هم ، اما در GPU ها چون هر GPU Die از تعداد زیادی هسته تشکیل شده که همزمان با هم کار می کنند، میتوان محاسبات رو روی اونها پخش کرد. مثلا 5 محاسبه ضرب در CPU تک هسته ای 5 کلاک لازم داشته باشه، در GPU ده هسته ای این 5 ضرب تنها با یک کلاک قابل محاسبه هستند. در نهایت هر چه کد رو بهینه بنویسید، این سخت افزار هستش که پیچیدگی زمانی اون رو تعیین میکنه.
رد میشه.نوشته شده توسط ژوپیتر
خداییش حوصله ندارم توضیح بدم.
این سه تا چیز رو راحع به روش کارش تحقیق کن.
bubble sort
merge sort
stxxl
منظورتون رو واضح بیان کنید، همون قدر که حوصله می کنید کامنتها رو بخونید برای نوشتنشون هم وقت بذارید، لطفا.
ok
اول این کلمه رو که آخر کار پست یادم اومد جست و جو کن و بخون.اگر نگرفتی همه پست رو بخون. :)
CPU Load Balancing
هشدار:تمامی کلمات انگلیسی استفاده شده برای این است که صفحات ویکیپدیا را بخوانید.لینک ها رو دنبال نکنید چون ممکن است یادتان برود کجا بودید.
۱.
CPU اصلاْ اونطوری که فکر میکنید نیست.(توی گوگل جست و جو کنید how cpu adds up two numbers in binary)
nstruction Setا ها برای رد حرف شما به وجود اومدن:
توی ویکیپدیا جست و جو کنید:
List Of Instruction Sets
بعد راجع به MMX و SSE بخونید.(فکر میکنم همین دو تا کافیه.ولی AES رو هم بخونی بد نیست.منظورم خود استاندارد نیست.منظورم سرعت instruction set ه)
بعد سایت گوگل که الگوریتم های سورت رو به شکل تصویری مقایسه میکنه ببینید.(اگر اسمش رو یادم بود که میگفتم.)
۲.
بعد برید توی بخش C++ و برنامه های نمونه رو ببینید.
یک نوع برنامه رو انتخاب کنید.(قصد توهین به هیچ گروهی رو ندارم.(خودشون میدونن.))مثل برنامه اعداد اول که من هم یکیش رو گزاشتم.
بعد سعی کنید benchmark بگیرید.
همه ی این برنامه ها یک کار میکنند و همشون با CPU خود شما اجرا میشن.ولی سرعت هیچ دوتایی برابر نیست.حافظه هیچکدوم هم برابر نیست.
بعد یک سری بزنید به CUDA و Stream.
وقتی همه رو خوندی بعد فکر کن مثلاْ که چه دلیلی داشته که اینتل
http://ark.intel.com/Product.aspx?id=53572
رو درست کرده.
۳.
بعد برو سراغ
Shared Memory
Threads
Lock
Synchronization
Semaphore/Mutex
Process
IPC
Message Passing
Erlang
HPC
BOINC
Clustering
Grid Computing
GridComputing in DBMSes
بعد که بیشتر صفحه ها رو توی ویکی پدیا خوندی(من هر کدوم رو ۱۰ بار خوندم/خیالت راحت باشه که کسی رو نمیکشه).متوجه میشی که اون سه تا کلمه به ترتیب معادل اینهاست:
سورت با یک ترد با الگوریتم وحشتناک
سورت با یک یا چند ترد(راه داره/توی ویکی نیست.) با یک روش بهینه.
و روش cluster(سورت با چند الگوریتم متفاوت در چند دستگاه با چند پردازنده)
فرق برنامه نویس خوب با بد همینه.
متاسفانه سایت گوگل اینجا فیلتره.وگرنه برای همه مطالب لینک میگزاشتم.
1- STXXL مربوط به کتابخانه نرم افزاری ++C هست و ربطی به کامنت اینجانب نداشت، اگر کامنت قبلی رو دوباره و با دقت مطالعه بکنید متوجه میشوید که اون مبحث در سطح پایین تر از STXXL هست و هم سطح Assembly است، یعنی جایی که داده ها تنها به صورت عملگر و عملوند هستند یا همون زبان ماشین.
2- CPU Load Balancing مربوط به تقسیم پردازش در CPU هست و باز هم ربطی به مطالب بالا نداشت، نحوه انجام محاسبات و پردازش یک پروسس با تقسیم کلاکهای پردازنده بین چند پروسس بسیار متفاوتند.
3- نیازی به جستجو در مورد "how cpu adds up two numbers in binary" نیست، بهتره کمی مطالعه داشته باشید، در هر CPU بخشی به اسم ALU هست که انجام عملیات ریاضی به عهده اونه و شما حتی اسمش رو هم ننوشتید، گفتم که برای نوشتن کامنت وقت بگذارید. ALU ها از انجام عملیات ریاضی اعشاری عاجز هستند و اینجاست که GPU ها خودنمایی میکنند چون پر از FPU هستند که مطلبی که بالا گذاشتم رو تایید میکنه چون CPU ها از هسته های کم و در نتیجه FPU های کمتری نسبت به GPU ها بر خوردارند. هر GPU Die از صدها هسته تشکیل شده که پردازش موازی رو امکان پذیرتر و زمان پردازش رو کاهش میده.
4- Instruction Set بر خلاف نظر اشتباه شما که دلیلش رو ننوشتید، صحت مطالب بالا رو تایید می کنند:
هر CPU Instruction از چند بخش تشکیل شده که هر قسمت مربوط به قسمتی از سیستم هست، OP code , Address و Data که نشانه این هست که در هنگام پردازش جمع دو عدد 128 بیتی در یک سیستم 32 بیتی باید چندین Instruction انجام شود تا یک عمل جمع انجام شود و تعدادی کلاک مختص عمل جمع میشود ولی در GPU ی مثلا 128 بیتی این عمل جمع با تعداد خیلی کمتری Instruction انجام شده، تعداد خیلی کمتری GPU Clock میگیرند.
5- List Of Instruction Sets مربوط به انواع Instruction های معماری های مختلف CPU هست و باز هم بی ربط به مطالب بالا بود، وقت بگذارید و با دلیل ادعای خودتون رو ثابت کنید، نوشتن چند لغت کافی نیست. مشخصه که از هر صفحه فقط پاراگراف اول رو خوندی و فکر کردی که دیگه یه دلیلی برای رد مطالب بالا پیدا کردی؟ ای شیطون
همون MMX رو دوباره و با دقت بیشتر بخون، در قسمتی چنین نوشته:
Each of the MMn registers holds 64 bits (the mantissa-part of a full 80-bit FPU register). The main usage of the MMX instruction set is based on the concept of packed data types, which means that instead of using the whole register for a single 64-bit integer, two 32-bit integers, four 16-bit integers, or eight 8-bit integers may be processed concurrently.
که باز هم مطالب بالا تایید میشه، برای جمع دو عدد 128 بیتی و یا انجام محاسبات بزرگتر، چون رجیسترها 64 بیتی هستند عملیات جمع به صورت Sequential h انجام شده و ابتدا یک عدد 128 بیتی با دو کلاک در MMX0 و MM1 قرار میگیره، با دو کلاک عدد دوم در MM2 و MM3 قرار میگیره و تازه حالا باید بریم سره FPU، حالا دوباره متن انگلیسی رو بخون، FPU تنها 80 بیت رو ظرفیت داره، پس چند کلاک دیگه لازمه که این عملیات جمع کامل بشه، پس بازهم عملیات برای انجام محاسبات ریاضی بزرگ به صورت پشت سر هم انجام میگیره یا همون Sequential. مثلا برای یک FFT 1024 سمپل، با تکنولوژی MMX در CPU این مشکل ظاهر میشه چون CPU مجبوره پردازشها رو بشکنه و در مقیاسهای کوچکتر و پشت سر هم انجام بده ولی در GPU ها بعضی از این قابلیتها، مثل انجام عملیات پیچیده ریاضی به صورت مدار منطقی پیاده سازی شده و با چند کلاک نا قابل پیچیده ترین عملیاتها رو انجام میدن.
SSE هم همینطور، باز هم مطالب بالا رو تایید میکنه، اصلا چرا SEE رو بحث کنم! میرم سر SSE 2 اون هم 64 بیت بیشتر Floating point محاسبه نمی کنه، تازه این نکته رو اضافه کنم که اگر FPU در CPU 32 بیتی یا 64 بیتی محاسبات اعشاری اعداد 128مثلا رو در یک کلاک هم انجام میداد(که نمیده) باز هم دچار مشکل پشت سر هم انجام دادن داده های بزرگ میشد، در GPU ها: تعداد هسته های بیشتر = موازی کاری بیشتر.
6- AES مربوط به رمزگذاری هست و ربطی به ALU نداره، مطالب بالا مربوط به ALU ها و FPU ها هستند که عملیات ریاضی در اونها انجام میشه نه رمزگذاری، لطفا از حاشیه پردازی خودداری کنید.
7- در مورد "بعد سایت گوگل که الگوریتم های سورت رو به شکل تصویری مقایسه میکنه ببینید." محاسبه پیچیدگی یک الگوریتم نسبت به شرایط تعریف شده و ثابت انجام میشه، مثلا AES 256بیتی برای شکسته شدن قفلش با پیچیدگی 2 به توان 99.5 بر روی یک CPU دو هسته ای ممکنه 4 سال طول بکشه ولی روی یک GPU با 150 هسته ممکنه دوماه طول بکشه که باز هم مطالب بالا رو تایید میکنه. پیچیدگی ثابت، انجام محاسبات پشت سرهم در CPU و محاسبات موازی در GPU.
-8 از مطلب 2 به بعد هم که با کامنت قبلی کاملا بی ارتباطه، یعنی منکه نفهمیدم ربطشو به این مطلب :
دوستان و مدیران اگه کسی چیزی فهمید، من رو هم بی خبر نذارید، ثواب داره..رد میشه.نوشته شده توسط ژوپیتر
در نهایت همه محاسبات شما به 4 عمل اصلی ختم میشه، چون در معماری CPU ها عملگرها بسیار ساده هستند و مانند GPU ها توان محاسبه های همزمان رو ندارند، به این دلیل که کد های شما در نهایت در تعداد محدودی Adder و Multiplier به صورت ترتیبی محاسبه میشه، چون تعداد هسته ها بسیار کمه، یعنی در نهایت مثل همون For Loop میشه، تکرار یک عمل پشت سر هم ، اما در GPU ها چون هر GPU Die از تعداد زیادی هسته تشکیل شده که همزمان با هم کار می کنند، میتوان محاسبات رو روی اونها پخش کرد. مثلا 5 محاسبه ضرب در CPU تک هسته ای 5 کلاک لازم داشته باشه، در GPU ده هسته ای این 5 ضرب تنها با یک کلاک قابل محاسبه هستند. در نهایت هر چه کد رو بهینه بنویسید، این سخت افزار هستش که پیچیدگی زمانی اون رو تعیین میکنه.
خداییش حوصله ندارم توضیح بدم.
این سه تا چیز رو راحع به روش کارش تحقیق کن.
bubble sort
merge sort
stxxl
بعد برید توی بخش C++ و برنامه های نمونه رو ببینید.
یک نوع برنامه رو انتخاب کنید.(قصد توهین به هیچ گروهی رو ندارم.(خودشون میدونن.))مثل برنامه اعداد اول که من هم یکیش رو گزاشتم.
بعد سعی کنید benchmark بگیرید.
همه ی این برنامه ها یک کار میکنند و همشون با CPU خود شما اجرا میشن.ولی سرعت هیچ دوتایی برابر نیست.حافظه هیچکدوم هم برابر نیست.
بعد یک سری بزنید به CUDA و Stream.
وقتی همه رو خوندی بعد فکر کن مثلاْ که چه دلیلی داشته که اینتل
http://ark.intel.com/Product.aspx?id=53572
رو درست کرده.
۳.
بعد برو سراغ
Shared Memory
Threads
Lock
Synchronization
Semaphore/Mutex
Process
IPC
Message Passing
Erlang
HPC
BOINC
Clustering
Grid Computing
GridComputing in DBMSes
بعد که بیشتر صفحه ها رو توی ویکی پدیا خوندی(من هر کدوم رو ۱۰ بار خوندم/خیالت راحت باشه که کسی رو نمیکشه).متوجه میشی که اون سه تا کلمه به ترتیب معادل اینهاست:
سورت با یک ترد با الگوریتم وحشتناک
سورت با یک یا چند ترد(راه داره/توی ویکی نیست.) با یک روش بهینه.
و روش cluster(سورت با چند الگوریتم متفاوت در چند دستگاه با چند پردازنده)
فرق برنامه نویس خوب با بد همینه.
متاسفانه سایت گوگل اینجا فیلتره.وگرنه برای همه مطالب لینک میگزاشتم.
۱.درسته.stxxl یک نمونه بود که به شما بگم روش و الگوریتم فرق داره.
۲.آره.ولی اسمش همونه.یک کوچولو فکر کن.
۳.خیر.حیف شد که مخابرات قم گوگل رو فیلتر کرده وگرنه لینکش رو میزاشتم.
۴.برای اینکه دوباره این حرف رو تکرار نکنی گفتم Load Balancing رو بخون.مخصوصاْ Advantages and disadvantages/performance gain/copy on write و ....
۵.این یعنی اینکه Instruction set ها سرعتشون و روش عملکردون فرق داره و تعداد Instruction Set ها از تعداد ۴ عمل اصلی که شما فرمودید بیشتره. Brain**** هم ۸ تا عملگر داره.
۶.توی پرانتز رو دوباره میخونی؟من گفتم منظورم رمز نگاری نیست.منظورم تعداد CPU Cycle هسات که از ۱۲.۵ برای هر بایت(نمیدونم برای چه سایزی بود/چرا گوگل فیلتره؟) کاهش پیدا کرده به یک عدد کمتر.
۷.چرا تصادفا هزیان میگی؟هنوز کسی AES-256 رو نشکسته.خوبه من گوگل ندارم تو داری.
اونها رو گفتم بخونی ذهنت باز بشه.
عجب متنی.یاد eshpilen افتادم.
@مدیران:خواهش میکنم مطلب رو پاک/قفل نکنید.
مشخصه که تاپیک هایی که شما در اون کامنت گذاشتید زیاد قفل شده که نگران هستید، مدیران کار خود را خوب می دانند.
از دوستان دعوت میکنم که کامنتها رو بخونن و نظرشون رو بنویسند، من بر مطالب مطرح شده توسط خودم پا فشاری نمی کنم، چون هرکسی لازم بدونه میره و در مورد اونها مطالعه میکنه.
در ضمن نحوه نوشتار شما نشانه نحوه افکار شماست.
؟!؟!؟نمیدونم.من دسترسی به دیتابیس سابت ندارم که mdev بگیرم.
در قوانین سایت آمده که وقتی بحث بیخودی که ربطی به موضوع اصلی تاپیک نداره میکنیم(دقت داشته باش که شما شروع کردی) و بحث رو به انحراف و دعوا میکشیم(اولی مطمئنا انجام شده) مدیران باید تاپیک رو قفل کنند یا پست های اضافه رو حذف کنند.ولی من میخوام ادامه بدیم که ببینیم آخرش چی میشه.یکی باید قانع بشه که اشتباه میکرده و باید یکم بیشتر مطالعه کنه.
لطفاٌ قوانین سایت رو بخونید.
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول