Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ike Naar <ike@iceland.freeshell.org> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: the language (and the role of Undefined Behavior therein) |
| Date | 2015-08-20 21:44 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <slrn3vfsmtcil7.bin.ike@iceland.freeshell.org> (permalink) |
| References | (12 earlier) <ek259a5e27tr5bel88c6o07qah84o349v1@4ax.com> <5492c298.300765@news.xs4all.nl> <ifilw.1128836$yK.904633@fx14.iad> <m74fij$csc$1@dont-email.me> <90183436-b839-4ee9-a3ed-a9eab341e847@googlegroups.com> |
On 2015-08-18, supercat@casperkitty.com <supercat@casperkitty.com> wrote:
> A major key to facilitating behavior-based optimization in usable
> programs is that it should be possible to write code whose behavior is
> sufficiently constrained to meet programmer requirements, but
> loosely-enough constrained to allow a compiler some flexibility.
> Consider the following requirements/function:
>
> /* Requirement 1: If the arithmetical values of a*b and c*d are
> both representable as int, return 1 if a*b > c*d
> and 0 otherwise. */
> int mulcomp(int a, int b, int c, int d)
> {
> return a*b > c*d;
> }
>
> Nice and simple, easy to read, and easy to optimize on a wide range of platforms. Now add one more requirement:
>
> /* Requirement 2: Do not negate the laws of time and causality, even if
> a*b or c*d is outside the range of int */
It is possible to compute a*b > c*d without computing the products a*b and c*d.
First, there are trivial cases where the result of the comparison only
depends on the signs of a,b,c,d, for instance, if a,b,c are positive but d is
negative, a*b > c*d evaluates to some_positive_value > some_negative_value which
is trivially true.
If no trivial cases apply, it is possible to re-arrange the expression such that
a,b,c,d are all positive and a>=b and c>=d, so that
a*b > c*d can be rewritten (taking quotients and remainders) to an
expression that tests the sign of (a/d - c/b) * b*d + (b * a%d - d * c%b), where
the first term, (a/d - c/b) * b*d, is a multiple of b*d, and the second term,
(b * a%d - d * c%b) has a magnitude less than b*d.
That means that if a/d == b/c, the first term equals zero and the result only
depends on the sign of b * a%d - d * c%b (which can be computed recursively),
and if a/d != b/c the second term can be neglected and the result only depends
on a/d - c/b.
See below is for a sketch of the algorithm:
#include <stdlib.h>
#include <assert.h>
static void swap(int *x, int *y)
{
int const t = *x; *x = *y; *y = t;
}
int mulcomp(int a, int b, int c, int d)
/* returns a*b > c*d without computing the products */
{
if ((a==0 || b==0) && (c==0 || d==0)) return 0;
if ((a==0 || b==0)) return (c>0) != (d>0);
if ((c==0 || d==0)) return (a>0) == (b>0);
assert(a!=0 && b!=0 && c!=0 && d!=0);
if ((a>0) == (b>0) && (c>0) != (d>0)) return 1;
if ((a>0) != (b>0) && (c>0) == (d>0)) return 0;
assert(((a>0) == (b>0)) == ((c>0) == (d>0)));
if ((a>0) != (b>0))
{
assert((c>0) != (d>0));
swap(&a, &c); swap(&b, &d);
}
a = abs(a); c = abs(c); b = abs(b); d = abs(d);
assert(0<a && 0<c && 0<b && 0<d);
if (a<b) swap(&a, &b);
if (c<d) swap(&c, &d);
assert(0 < b && b <= a && 0 < d && d <= c);
div_t const ad = div(a, d), cb = div(c, b);
return ad.quot == cb.quot ? mulcomp(b, ad.rem, d, cb.rem) : ad.quot > cb.quot;
}
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-18 16:19 -0700
Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-18 21:15 -0400
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 10:11 -0700
Re: the language (and the role of Undefined Behavior therein) Ike Naar <ike@iceland.freeshell.org> - 2015-08-19 19:58 +0000
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 14:09 -0700
Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-19 16:10 -0400
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-19 16:01 -0700
Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-19 20:23 -0400
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 10:35 -0700
Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-20 12:32 -0700
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 13:31 -0700
Re: the language (and the role of Undefined Behavior therein) donalhambra@gmail.com - 2015-08-20 14:23 -0700
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 16:13 -0700
Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-20 17:48 -0700
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-21 01:32 -0700
Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-21 18:34 -0700
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-21 22:11 -0700
Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-22 09:41 -0400
Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-22 16:59 +0000
Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-22 23:30 -0400
Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 03:36 +0000
Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 00:25 -0400
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 22:57 -0700
Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 19:49 +0000
Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-06 14:43 -0700
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 16:27 -0700
Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 21:15 -0400
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 20:18 -0700
Re: the language (and the role of Undefined Behavior therein) raltbos@xs4all.nl (Richard Bos) - 2015-08-22 14:37 +0000
Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-22 19:12 -0700
Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-22 23:38 -0400
Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-23 20:01 -0700
Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-23 21:56 -0700
Re: the language (and the role of Undefined Behavior therein) David Kleinecke <dkleinecke@gmail.com> - 2015-08-24 17:25 -0700
Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-24 18:21 -0700
Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 22:22 -0400
Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-25 14:31 +0000
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-25 09:22 -0700
Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-25 18:55 +0000
Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-25 12:33 -0700
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-25 16:23 -0700
Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-24 00:31 -0400
Re: the language (and the role of Undefined Behavior therein) Keith Thompson <kst-u@mib.org> - 2015-08-24 10:32 -0700
Re: the language (and the role of Undefined Behavior therein) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-22 23:54 -0700
Re: the language (and the role of Undefined Behavior therein) glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-08-24 03:45 +0000
Re: the language (and the role of Undefined Behavior therein) Tim Rentsch <txr@alumni.caltech.edu> - 2015-09-07 08:11 -0700
Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 18:46 -0400
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 19:04 -0700
Re: the language (and the role of Undefined Behavior therein) Richard Damon <Richard@Damon-Family.org> - 2015-08-23 23:40 -0400
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-23 22:48 -0700
Re: the language (and the role of Undefined Behavior therein) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-08-24 00:38 -0700
Re: the language (and the role of Undefined Behavior therein) James Kuyper <jameskuyper@verizon.net> - 2015-08-18 21:22 -0400
Re: the language (and the role of Undefined Behavior therein) Ike Naar <ike@iceland.freeshell.org> - 2015-08-20 21:44 +0000
Re: the language (and the role of Undefined Behavior therein) supercat@casperkitty.com - 2015-08-20 16:48 -0700
Re: the language (and the role of Undefined Behavior therein) Philip Lantz <prl@canterey.us> - 2015-08-20 23:41 -0700
csiph-web