Post new article in this section History Correct this article See also Which function is faster? 20

A compendium of Delphi Delphi 7 Compendium programmer Delphi 2005. Compendium programmer Articles cash FAQ C / C + + Articles FAQ C # Introduction to C # PHP FAQ Python Java Turbo Pascal with borderline FAQ Assembler Algorithms (X) HTML CSS Forum Newbie Delphi / Pascal C / C + +, C # and. NET Java PHP Webmastering Other programming languages Databases Algorithms and Data Structures Software Engineering Unusual Topics Education Career Training & Events Programmer Magazine Off-Topic Hardware / Software Community Flame Coyote Pastebin microblogs 2 gallon jar Jobs
Post new article in this section History Correct this article See also Which function is faster? 2011-01-15 10:41 I do not have Delphi 7, and the example is a function PosEx. Where to get it 2011-03-06 8:17 How to measure the operation time 2002-10-17 17:43 optimizations in Delphi 2 gallon jar (example - Part II) 2009-07-12 1:31 Asm 2006-08-09 18:16 Assembler ATamp, T and inserts in the GCC Mod rewrite 2005-01-02 21:52 2008-02-05 23:54 How to get the CPU clock frequency 2006-02-15 15:29 2007-04-14 13:39 Register Factorial - High-DIV and MOD 2006-11-05 12:27
A long time ago ... This one guy called Euclid invented the method of finding the greatest common divisor of two numbers (called the Greatest Common Divisor). 1 We have two numbers u and v 2 If the numbers are equal, the gcd (u, v) = u 3 If u> v then u: = u - vi go to step 2 3 If u <v then v: = v - u and go to step 2 If it's so simple we write a function that computes us using recursion: function GcdOd (u, v: Cardinal): Cardinal; begin if v> u then Result: = GcdOd (u, v - u) if v <u then Result: = GcdOd (u - v, v) if u = v then Result: = v; end; GcdOd (1000, 2132424); Average Execution time: 40457 clock cycles Cool, but a little long faces (call it tens of thousands of times ) How is this a good look at this subtraction, we can replace 2 gallon jar the remainder of dividing one number by another and wyowływać alternate function. If u <v is uv = u mod v if u> v then u mod v = u and no change. GcdR function (u, v: Cardinal): Cardinal; begin if v = 0 then Result: = u else Result: 2 gallon jar = GcdR (v, u mod v) end; GcdR (1000, 2132424); Average Execution time: 399 cycles Clock About this feature works much faster (101 times faster) But if this can not be a little more speed? 2 gallon jar As you know every recursive function (producing itself) can be processed into iterative functions (uses loops). Iterative 2 gallon jar functions are generally faster, but compared to the recursive typically are less clear and consume more memory. Let's try this: function GcdI (u, v: Cardinal): Cardinal; var p: Integer; begin while v <> 0 do begin t: = u mod v, u: = v, v: = t; end; Result: = u , end; GcdI (1000, 2132424); Average Execution time: 360 clock cycles pretty good. We have gained about 10% speed. What else can I speed this up? Can write everything in assembler? Although compilers usually perfectly optimize the code, it is not like human contribution: function GcdASM (u, v: Cardinal): Cardinal; asm {in edx is v, and eax is u} push ebx / / if there was something that we put on stack mov ecx, edx / / move v to ecx, because we will need edx / / if v = 0 to the end of the test ecx, ecx jz @ end @ the beginning: xor eax, eax / / here is the rest, so zero the registry div ecx / / divide by v. Shared number is in eax, ecx divider in a / / t: = u mod v t is our edx mov eax, ecx / / u: = v mov ecx, edx / / v: = t / / if v <> 0 is the beginning of the test ecx, ecx jnz @ @ beginning of the end: / / Result: = u, ie, eax: = u; pop ebx / / take off the original value from the stack end; GcdOd (1000, 2132424); Average Execution time: 348 clock cycles (and even 1%) As you can see the algorithm is very ingenious, but it can spoil the bad writing 2 gallon jar function ...
rafcio88_put: After GCD (12, 24, 6) = GCD (12, NWD (24, 6)), and it's simple to implement. 1 Get an array of A 2 Set the value of the variable and the length of the array A 3 While I> 0 (1 in Delphi) a set value of the array element A No. I-1 to NWD (the value of the array element A No. I, the value of the array element A No. I-1) b remove the array element number and ao c Reduce And 1 4 Note the value of the first element of the array A
You might be interested so here ultaszybka version of gcd: template <long x, long y> gcd struct {static const long value = gcd <y,x%y> :: value;} template struct <long x> gcd <x, 0 > {static const long value = x;} int main (int argc, char * argv []) {long s = gcd <1000 2132424> :: value, return 0;}
bati87: do not laugh, after all, it's almost like pseudo code, just think you need a little ... 1) GcdR function (u, v: Cardinal): Cardinal substitute for eg: int GcdR (int