473,573 Members | 2,792 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Efficient division/remainder in C

I can't find any discussion of this question in this NG.

I'd like to implement some variable precision integer arithmetic in C,
and do it efficiently. A problem arises with the divide/remainder
operations. I'm using gcc on x86, but a lot of what I say applies to
other architectures.

First, I assume the div and ldiv functions are more efficient than
using / and % (obviously it depends on the compiler and level of
optimization, but it's one operation instead of two).

However, div and ldiv require the length of the quotient, divisor,
dividend and remainder to all be the same. Now all the machines I've
ever worked with at the machine language level (quite a few of them)
implement integer division with a dividend that is twice as long as the
divisor, quotient and remainder. Moreover, this is what naturally
arises in multiple precision arithmetic, you get dividends twice as
long as everything else. So suppose I'm using 16-bit divisors,
quotients and remainders, but 32-bit dividends. If I were writing in
assembly language, I would use the instructions that divide 16 bits
into 32.

But when I write in C, I'm forced to use the ldiv function, since one
of the operands is 32-bits. (Let's say int=16-bit and long=32-bit, as
on my machine.) Then the compiler has to implement this ldiv function
by using the instruction that divides 32-bits into 64-bits, since the
divisor is now 32-bits. In other words, the compiled code is forced to
use a divide instruction with operands twice as large as needed, due to
the design of the div and ldiv functions.

Anybody know a way around this (apart from inserting assembly code in
my C program)?

Thanks in advance...

Jan 13 '06 #1
29 5872


ne*****@wigner. berkeley.edu wrote On 01/13/06 17:47,:
[...]
First, I assume the div and ldiv functions are more efficient than
using / and % (obviously it depends on the compiler and level of
optimization, but it's one operation instead of two).
[...]
But when I write in C, I'm forced to use the ldiv function, since one
of the operands is 32-bits. (Let's say int=16-bit and long=32-bit, as
on my machine.) Then the compiler has to implement this ldiv function
by using the instruction that divides 32-bits into 64-bits, since the
divisor is now 32-bits. In other words, the compiled code is forced to
use a divide instruction with operands twice as large as needed, due to
the design of the div and ldiv functions.


The leap from "I assume" to "I'm forced" seems a
risky one. What have your measurements shown about
the efficiencies of /, %, both / and %, and ldiv?

You *have* made measurements, haven't you?

HAVEN'T YOU????

--
Er*********@sun .com

Jan 13 '06 #2
Use inline assembly for the system you are on. Use macros to determine
which routine depending on your system. Burst into flames.

ne*****@wigner. berkeley.edu wrote:
I can't find any discussion of this question in this NG.

I'd like to implement some variable precision integer arithmetic in C,
and do it efficiently. A problem arises with the divide/remainder
operations. I'm using gcc on x86, but a lot of what I say applies to
other architectures.

First, I assume the div and ldiv functions are more efficient than
using / and % (obviously it depends on the compiler and level of
optimization, but it's one operation instead of two).

However, div and ldiv require the length of the quotient, divisor,
dividend and remainder to all be the same. Now all the machines I've
ever worked with at the machine language level (quite a few of them)
implement integer division with a dividend that is twice as long as the
divisor, quotient and remainder. Moreover, this is what naturally
arises in multiple precision arithmetic, you get dividends twice as
long as everything else. So suppose I'm using 16-bit divisors,
quotients and remainders, but 32-bit dividends. If I were writing in
assembly language, I would use the instructions that divide 16 bits
into 32.

But when I write in C, I'm forced to use the ldiv function, since one
of the operands is 32-bits. (Let's say int=16-bit and long=32-bit, as
on my machine.) Then the compiler has to implement this ldiv function
by using the instruction that divides 32-bits into 64-bits, since the
divisor is now 32-bits. In other words, the compiled code is forced to
use a divide instruction with operands twice as large as needed, due to
the design of the div and ldiv functions.

Anybody know a way around this (apart from inserting assembly code in
my C program)?

Thanks in advance...


Jan 13 '06 #3
On 2006-01-13, ne*****@wigner. berkeley.edu <ne*****@wigner .berkeley.edu> wrote:
I can't find any discussion of this question in this NG.

I'd like to implement some variable precision integer arithmetic in C,
and do it efficiently. A problem arises with the divide/remainder
operations. I'm using gcc on x86, but a lot of what I say applies to
other architectures.

First, I assume the div and ldiv functions are more efficient than
using / and % (obviously it depends on the compiler and level of
optimization, but it's one operation instead of two).
Not really - it requires a function call and use of a structure, and any
compiler should optimize use of / and % with the same operands anyway.
But when I write in C, I'm forced to use the ldiv function, since one
of the operands is 32-bits. (Let's say int=16-bit and long=32-bit, as
on my machine.) Then the compiler has to implement this ldiv function
by using the instruction that divides 32-bits into 64-bits, since the
divisor is now 32-bits. In other words, the compiled code is forced to
use a divide instruction with operands twice as large as needed, due to
the design of the div and ldiv functions.
i'm pretty sure that there are instructions on x86 take 32 bits for both
operands.
Anybody know a way around this (apart from inserting assembly code in
my C program)?


just use / and %.
Jan 14 '06 #4
You are right. Suppose I have declarations
unsigned int quot,rem,dvsr;
unsigned long dvnd;
and then I say
quot=dvnd/dvsr;
rem =dvnd%dvsr;

If the compiler is smart enough to generate a single divide instruction
(that's all that's required on the x86 hardware), then I have what I
want.

Maybe I will try to figure out how to list assembly output from gcc to
see what instructions it actually generates.

Thanks for the reply!

Jan 14 '06 #5
On 2006-01-14, ne*****@wigner. berkeley.edu <ne*****@wigner .berkeley.edu> wrote:
Maybe I will try to figure out how to list assembly output from gcc to
see what instructions it actually generates.


<OT>gcc -S</OT>
Jan 14 '06 #6
ne*****@wigner. berkeley.edu writes:
You are right. [...]

About what? Most of us can't easily see the article to which you're
replying. Please read <http://cfaj.freeshell. org/google/>.

[...]
Maybe I will try to figure out how to list assembly output from gcc to
see what instructions it actually generates.


<OT>
gcc -S
</OT>

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jan 14 '06 #7

Jordan Abel wrote:
On 2006-01-13, ne*****@wigner. berkeley.edu <ne*****@wigner .berkeley.edu> wrote:
First, I assume the div and ldiv functions are more efficient than
using / and % (obviously it depends on the compiler and level of
optimization, but it's one operation instead of two).


Not really - it requires a function call and use of a structure, and any
compiler should optimize use of / and % with the same operands anyway.

just use / and %.


Some of the responses make me wonder if your question was understood.
You want both "/" and "%" but don't want to needlessly repeat the
division. Do compilers find this optimization?

Someone from Sun implies that speed comparison tests are appropriate.
He should preach this in-house. It was trivial to beat memcpy() on
Sun-3 (which was optimized for Sun-2). The early Sparc's integer
multiply
could not only be bettered by rewriting the assembly, it *could be
beaten
without assembly in a C routine!* (In either way the speed improvement
was huge.)

James

Jan 14 '06 #8
Keith Thompson wrote:
ne*****@wigner. berkeley.edu writes:

[...]
Maybe I will try to figure out how to list assembly output from gcc to
see what instructions it actually generates.


<OT>
gcc -S
</OT>

I use: gcc -gstabs+ -Wa,-ahldn -c

and pipe the result to less.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>
Jan 14 '06 #9
James Dow Allen wrote:
Someone from Sun implies that speed comparison tests are appropriate.
He should preach this in-house. It was trivial to beat memcpy() on
Sun-3 (which was optimized for Sun-2).


How many employees from 20 years ago do you think are still there? :-)

- Logan
Jan 14 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
1833
by: Michael Cornelius | last post by:
As an old C programmer, I'm surprised by some results I'm getting with integer division. For example: >>> -1/1000 -1 >>> -9/2 -5 I expect the results of these expressions to be 0 and -4, respectively.
1
26563
by: Dave | last post by:
Hi, Doe it exist a similar function or operator like 'mod' in VBscript in order to get the remainder of a division? Thanks dave
24
19311
by: Teis Draiby | last post by:
In .NET, can I be sure that the result of a division between two integers always is truncated rather that rounded to nearest? Example: 99 / 50 = 1 regards, Teis
5
977
by: silentlights | last post by:
Hi, Is there a possibiliy to improve division or Modulo operations in the following, tmp1 = 123; tmp2 = 123; frame = ((char)((tmp1/100)+48)); // Division tmp1 = (tmp2 % 100); // Mod frame = ((char)((tmp1/10)+48)); tmp1 = (tmp2 % 10);
17
2401
by: seb.haase | last post by:
Hi, Is it true that that "Python 3000" is dead ? Honestly I think that e.g. changing 5/2 to be 2.5 (instead of 2) would just break to much code :-( On the otherhand I'm using Python as "Matlab replacement" and would generally like 5/2 ==2.5 So, I was contemplating to default all my modules/scripts to start with "from __future__ import...
22
5794
by: jamestuck21 | last post by:
Hi, I'm trying to work out a binary division problem 1100 / 101010101010111 Here is what I have so far but I'm not sure if I'm doing it correctly and I'm suppose to continue the division until there is only a remainder left
13
7104
by: jamesonang | last post by:
Supposed unsigned int(32 bits) is the largest number that computer can represent with a single variable. Now, i have a big integer ( less than 64 bit, but great than 32 bit) . i represent it by this way: unsigned int dividend : divident store low 32 bits of big integer, dividend store high 32 bits of big integer.
2
2052
by: Jankie | last post by:
hello everyone am trying to insert a division calculation into a mysql column but am unable to get mysql render the result together with the remainder. I understand i can get the remainder with the Mod or % operator,but that only returns the remainder alone i want 18/180 to return 0.1 or 0.10 how can i do this currently it returns 0 ( no odd...
16
5260
by: spl | last post by:
To increase the performance, how to change the / operator with bitwise operators? for ex: 25/5, 225/25 or 25/3 or any division, but I am not bothered of any remainder.
0
7760
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7679
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
8191
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
0
8049
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6392
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5573
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5284
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
1
2185
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
0
1029
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.