## Re: [Sdcc-user] need a very fast 18bit / 15bit div

 Re: [Sdcc-user] need a very fast 18bit / 15bit div From: Scott Dattalo - 2002-03-20 14:19:49 ```On Wed, 20 Mar 2002, Bernhard Held wrote: > > Does anybody know where to find source of a very fast division of 18bit / > > 15bit ? > What processor? For the 8051you'll find assembler functions for 16/16 and > 32/32 bit divisions in the library. It should be easy to adjust the source > for 18/15 bit. Additionally you can eliminate the loop. AFAIK there is no > faster algorithm for the 8051, if there's no further infomation about the > distribution of the values. Yeah, which processor? There are always tricks one can play. A generic solution to this problem would be to un-roll the division loop. This saves decrementing a loop counter and a branch. If you know something about the form of the numbers, there are additional tricks. For example, if your divisor is actually a constant, then it's often faster to multiply by it's reciprocal. Or if you know that the upper bits are constant, then you can try this formula: x/y = x / (y_up + y_lo) = x / y_up * (1/(1 + y_lo/y_up)) A series expansion of 1 -------- = 1 - A + A^2 - A^3 1 + A May be then invoked. This is especially useful for the case when y_up is way greater than y_lo because then only a few terms of the expansion are needed. Intelligent partitioning can turn some of the division operations into shift operations. There are many, many tricks. But each trick depends on the specific problem to be solved. Scott ```

 [Sdcc-user] need a very fast 18bit / 15bit div From: Schmitt Michael - 2002-03-20 08:17:56 ```Does anybody know where to find source of a very fast division of 18bit / 15bit ? did i write very fast ? yes i mean very fast, as fast as possible. Thanks in advance. Dipl.-Ing. (FH) Michael Schmitt Baumer Ident GmbH Entwicklung / Development Department Hertzstr. 10 D-69469 Weinheim Deutschland / Germany Tel. +49 (0) 6201 9957 - 30 Fax. +49 (0) 6201 9957 - 99 E-Mail : mschmitt@... Web: http://www.baumerident.com ```
 Re: [Sdcc-user] need a very fast 18bit / 15bit div From: Bernhard Held - 2002-03-20 13:45:15 ```> Does anybody know where to find source of a very fast division of 18bit / > 15bit ? What processor? For the 8051you'll find assembler functions for 16/16 and 32/32 bit divisions in the library. It should be easy to adjust the source for 18/15 bit. Additionally you can eliminate the loop. AFAIK there is no faster algorithm for the 8051, if there's no further infomation about the distribution of the values. Bernhard ```
 Re: [Sdcc-user] need a very fast 18bit / 15bit div From: Scott Dattalo - 2002-03-20 14:19:49 ```On Wed, 20 Mar 2002, Bernhard Held wrote: > > Does anybody know where to find source of a very fast division of 18bit / > > 15bit ? > What processor? For the 8051you'll find assembler functions for 16/16 and > 32/32 bit divisions in the library. It should be easy to adjust the source > for 18/15 bit. Additionally you can eliminate the loop. AFAIK there is no > faster algorithm for the 8051, if there's no further infomation about the > distribution of the values. Yeah, which processor? There are always tricks one can play. A generic solution to this problem would be to un-roll the division loop. This saves decrementing a loop counter and a branch. If you know something about the form of the numbers, there are additional tricks. For example, if your divisor is actually a constant, then it's often faster to multiply by it's reciprocal. Or if you know that the upper bits are constant, then you can try this formula: x/y = x / (y_up + y_lo) = x / y_up * (1/(1 + y_lo/y_up)) A series expansion of 1 -------- = 1 - A + A^2 - A^3 1 + A May be then invoked. This is especially useful for the case when y_up is way greater than y_lo because then only a few terms of the expansion are needed. Intelligent partitioning can turn some of the division operations into shift operations. There are many, many tricks. But each trick depends on the specific problem to be solved. Scott ```