Greatest number divisible by Y

[Frederick Gotham]

I'm trying to devise a compile-time constant for X, where X is the
greatest number which satisfies both the following criteria:

(1) X <= DESIGNATED_MAX_ VALUE

(2) X % Y == 0
I'll try to explain with example code:
#define MAX_DIVISIBLE(m ax,divisor) /* Something */

int main(void)
{
unsigned long max = -1;

unsigned long max_divisible_b y_10 = MAX_DIVISIBLE(m ax,10);
}
On a system where unsigned long has 32 value bits, the variables should
get the following values:

max == 4294967295
max_divisible_b y_10 == 1000000000
Has anyone ever written such a macro? If not, can anyone please give
pointers?
--

Frederick Gotham

[Old Wolf]

Frederick Gotham wrote:

I'm trying to devise a compile-time constant for X, where X is the
greatest number which satisfies both the following criteria:

(1) X <= DESIGNATED_MAX_ VALUE

(2) X % Y == 0
#define MD(max, divisor) ( (max) - (max) % (divisor) )

max == 4294967295
max_divisible_b y_10 == 1000000000

Should be 4294967290, unless you are using some new meaning
of 'divisible' that you aren't telling us

[Richard Heathfield]

Frederick Gotham said:

I'm trying to devise a compile-time constant for X, where X is the
greatest number which satisfies both the following criteria:

(1) X <= DESIGNATED_MAX_ VALUE

(2) X % Y == 0

#define MAX_DIVISIBLE(m , d) (m / d) * d

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Frederick Gotham]

Old Wolf posted:

max == 4294967295
max_divisible_b y_10 == 1000000000

Should be 4294967290, unless you are using some new meaning
of 'divisible' that you aren't telling us

(I suggest using a mono-space font for reading this.)
You're correct, I worded it wrongly.

I'll try again. (I'll try to think of it in terms of inputs, processes,
and outputs).

Here are the inputs:

max_value: 4294967295
divisor: 10
Here's the desired output:

1000000000

I think the output I'm looking for is the greatest number which satisfies
the two following criteria:

(1) output <= max_value
(2) Log-base-divisor of output is an exact integer.
Here are some sample inputs and outputs:

Inputs: 237509275
10

Output: 100000000
Inputs: 98722
10

Output: 10000
Inputs: 9270720
10

Output: 1000000
Inputs: 45
10

Output: 10

Inputs: 4648
10

Output: 1000

--

Frederick Gotham

[Skarmander]

Frederick Gotham wrote:

> Old Wolf posted:

>>> max == 4294967295
max_divisible_b y_10 == 1000000000

Should be 4294967290, unless you are using some new meaning
of 'divisible' that you aren't telling us

(I suggest using a mono-space font for reading this.)
You're correct, I worded it wrongly.

I'll try again. (I'll try to think of it in terms of inputs, processes,
and outputs).

Here are the inputs:

max_value: 4294967295
divisor: 10
Here's the desired output:

1000000000

I think the output I'm looking for is the greatest number which satisfies
the two following criteria:

(1) output <= max_value
(2) Log-base-divisor of output is an exact integer.

In other words, for some base b, you want to round to the nearest power of b
that's at most your input. Something like pow(b, floor(log(n) / log(b))) for
some base b and some n > 0?

You can't possibly hope to do that at compile time. Fast algorithms exist
for rounding to integer powers (especially for the case b = 2), but none of
them yield compile-time constants, certainly not if b isn't known a priori.

My advice is to look at what you're doing and make sure you 1) really need a
compile-time constant for that and 2) you can't manage with a guess that's
"good enough" and 3) you really want the value you're after and can't change
the algorithms/data structures that depend on it.

S.

[Martin Golding]

On Sat, 01 Jul 2006 17:29:43 +0000, Frederick Gotham wrote:

You're correct, I worded it wrongly.

I'll try again. (I'll try to think of it in terms of inputs, processes,
and outputs).

Here are the inputs:
max_value: 4294967295
divisor: 10

Here's the desired output:

1000000000

I think the output I'm looking for is the greatest number which satisfies
the two following criteria:

(1) output <= max_value
(2) Log-base-divisor of output is an exact integer.

Here are some sample inputs and outputs:

Inputs: 237509275
10
Output: 100000000

Inputs: 98722
10
Output: 10000

Inputs: 9270720
10
Output: 1000000

This is a vile disgusting macro, and is quite optimistic about your
compiler's optimization and macro processing capability. It will get
even more uglier if you insist on max_value much larger than int32_t.

I have implemented the macro for divisor=2 where max_value is < 2^16,
and for 9 and 10 where max_value is <= 2^31. I had no idea what to do
about max_value < divisor, or either < 0. Further expansion is left
as an exercise for the reader.

If your compiler will forgive integer overflow and you don't mind
scads of warnings, you can use just a single set, scaled for your
smallest expected divisor and largest expected max_value.

It might be worth considering whether something sensible could be
constructed with short circuit evaluation, and seeing whether your
compiler prints warnings about expressions that won't ever be executed.

The 'shape' of the macro makes it easy to see if a line has been
mistyped, ommitted or repeated. It is not Christmas yet.

#include <stdio.h>
#include <limits.h>

#define maxPowerOf(X,Y) ( \
Y < 2? -1 \
:Y < 3?( \
X < Y ? 1:\
X < Y*Y ? Y:\
X < Y*Y*Y ? Y*Y:\
X < Y*Y*Y*Y ? Y*Y*Y:\
X < Y*Y*Y*Y*Y ? Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y ? Y*Y*Y*Y*Y*Y*Y*Y :\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y* Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y: \
Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y* Y) \
/* Much fiddle faddle skiped here */ \
:Y< 11?( \
X < Y ? 1: \
X < Y*Y ? Y:\
X < Y*Y*Y ? Y*Y:\
X < Y*Y*Y*Y ? Y*Y*Y:\
X < Y*Y*Y*Y*Y ? Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y ? Y*Y*Y*Y*Y*Y*Y*Y :\
Y*Y*Y*Y*Y*Y*Y*Y *Y) \
/* More fiddle faddle skipped here */ \
:-1) /* remaining divisors unimplemented */

#define show(X,Y) \
printf("Inputs: %10d\n %10d\nOutputs: %10d\n\n", \
X, Y, maxPowerOf(X,Y) )
int
main(void)
{
show(237509275, 10);
show(98722, 10);
show(9270720, 10);
show(INT_MAX,10 );

show(1,2);
show(1000,2);
show(10000,2);
show(65535,2);
show(100000,2);

return 0;
}
This is not helpful, because you really shouldn't do that, but it
was kinda fun.

Martin
--
Martin Golding | C compilers exist in which sizeof(long) == 1.
fo*****@comcast .net | Are they "both-endian", or "neither-endian"?

[Frederick Gotham]

Martin Golding posted:

This is not helpful, because you really shouldn't do that, but it
was kinda fun.

Thanks, it will hold me over for the moment.

I think I'll start practising writing macros like that, it could come in
handy, and above it all it might be fun!
[OFF-TOPIC from here on]

I'm actually writing a C++ template, and such a macro would allow me to
write:

template<class T>
class UnsignedNumeric TypeInfo {
public:

static T const max_power_of_te n = maxPowerOf( (T)-1, 10 );
};
rather than having to go the non-portable, verbose method of:
typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned int uint32;
typedef unsigned long long uint64;

template<class T>
class UnsignedNumeric TypeInfo {};

template<>
class UnsignedNumeric TypeInfo<uint32 >
{
static uint32 const max_power_of_te n = 1000000000;
};

template<>
class UnsignedNumeric TypeInfo<uint16 >
{
static uint32 const max_power_of_te n = 10000;
};
/* And so forth */
Now my code will work if compiled on a 36-Bit machine. : )
--

Frederick Gotham

[Martin Golding]

On Sun, 02 Jul 2006 12:37:01 +0000, Frederick Gotham wrote:

Martin Golding posted:

>This is not helpful, because you really shouldn't do that, but it was
kinda fun.

Thanks, it will hold me over for the moment.

It's BROKE! see below for details, and a working (and simplified) version.

I think I'll start practising writing macros like that, it could come in
handy, and above it all it might be fun!

It IS fun, but it is generally NOT a Good Idea. Though I have done a
few not _quite_ so repulsive things in production code, such things
should be done with the appropriate sense of fear and trembling.

[OFF-TOPIC from here on]
I'm actually writing a C++ template, and such a macro would allow me to
write:

template<class T>
class UnsignedNumeric TypeInfo {
public:

static T const max_power_of_te n = maxPowerOf( (T)-1, 10 );
};

If all you want is powers-of-10, there is another option, quite more
repulsive yet beautiful in the way of Rodin's "Belle Heauimiere".
------------------------------------
#include <stdio.h>
#include <limits.h>

/* This macro calculates the highest power of 10 less than X */
/* X _must be_ 0 and have no leading 0 */

static int powersOfTen[] =
{ 1
, 10
, 100
, 1000
, 10000
, 100000
, 1000000
, 10000000
, 100000000
,1000000000
};

/* Returns the power of 10 with the same number of digits as X */
#define maxPowerOfTen(X ) (powersOfTen[sizeof(#X)-2])

#define show(X) \
printf("Inputs: %10d\nOutputs: %10d\n\n", X, maxPowerOfTen(X ))
int
main(int argc, char *argv[])
{
show(0);
show(9);
show(98722);
show(9270720);
show(237509275) ;
show(INT_MAX);

return 0;
}
------------------------------------
Inputs: 0
Outputs: 1

Inputs: 9
Outputs: 1

Inputs: 98722
Outputs: 10000

Inputs: 9270720
Outputs: 1000000

Inputs: 237509275
Outputs: 100000000

Inputs: 2147483647
Outputs: 1000000000
------------------------------------
My original macro had a horrible bug, and was much more complicated
than necessary. If max_value was greater than INT_MAX/divisor, the
highest power of divisor greater than max_value could not be
calculated. Copious warnings were produced, which (being groggy) I
fixed by reducing the table size for larger values, which didn't
solve the problem but avoided the errors for the test cases.

Here's the New and Improved version implemented for divisors >=9.
To extend that to divisors >= 2, the number of lines in each section
must be expanded to log_base_mindiv isor(max maxvalue), eg,
log2(LONG_MAX), 63 on a well-mannered compiler.

I _could_ calculate the power expressions as long and drop the second
half of the macro, but that just postpones the problem. If the range
of max_value exceeds int_max, the power expressions (Y*Y..) should be
cast to (_calculated as_, take care where the cast is) an integer
type that can hold the maximum desired max_value.

------------------------------------
#include <stdio.h>
#include <limits.h>

/* This macro calculates the highest power of Y less than X */
/* It oes not handle Y=0 or Y=1 or Y>X */
#define maxPowerOf(X,Y) ( \
/* If X is less than INT_MAX/Y, find the highest power of Y < X */ \
X < INT_MAX/Y? \
( \
X < Y ? 1: \
X < Y*Y ? Y:\
X < Y*Y*Y ? Y*Y:\
X < Y*Y*Y*Y ? Y*Y*Y:\
X < Y*Y*Y*Y*Y ? Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y ? Y*Y*Y*Y*Y*Y*Y*Y :\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y:\
X < Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y* Y ? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y: \
Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y* Y \
) \
: \
/* Y INT_MAX/X: find the highest power of Y < INT_MAX. */ \
( \
Y INT_MAX/Y? Y: \
Y*Y INT_MAX/Y? Y*Y: \
Y*Y*Y INT_MAX/Y? Y*Y*Y: \
Y*Y*Y*Y INT_MAX/Y? Y*Y*Y*Y: \
Y*Y*Y*Y*Y INT_MAX/Y? Y*Y*Y*Y*Y: \
Y*Y*Y*Y*Y*Y INT_MAX/Y? Y*Y*Y*Y*Y*Y: \
Y*Y*Y*Y*Y*Y*Y INT_MAX/Y? Y*Y*Y*Y*Y*Y*Y: \
Y*Y*Y*Y*Y*Y*Y*Y INT_MAX/Y? Y*Y*Y*Y*Y*Y*Y*Y : \
Y*Y*Y*Y*Y*Y*Y*Y *Y INT_MAX/Y? Y*Y*Y*Y*Y*Y*Y*Y *Y: \
Y*Y*Y*Y*Y*Y*Y*Y *Y*Y INT_MAX/Y? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y: \
Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y INT_MAX/Y? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y: \
Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y INT_MAX/Y? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y: \
Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y INT_MAX/Y? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y: \
Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y INT_MAX/Y? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y: \
Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y INT_MAX/Y? Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y: \
Y*Y*Y*Y*Y*Y*Y*Y *Y*Y*Y*Y*Y*Y*Y* Y \
) \
)

#define show(X,Y) \
printf("Inputs: %10d\n %10d\nOutputs: %10d\n\n", \
X, Y, maxPowerOf(X,Y) )
int
main(int argc, char *argv[])
{
show(1000,2);
show(10000,2);
show(65535,2);
show(100000,2);

show(98722, 10);
show(9270720, 10);
show(237509275, 10);
show(INT_MAX,10 );

show(INT_MAX,IN T_MAX);

return 0;
}
------------------------------------
Inputs: 1000
2
Outputs: 512

Inputs: 10000
2
Outputs: 8192

Inputs: 65535
2
Outputs: 32768

Inputs: 100000
2
Outputs: 65536

Inputs: 98722
10
Outputs: 10000

Inputs: 9270720
10
Outputs: 1000000

Inputs: 237509275
10
Outputs: 1000000000

Inputs: 2147483647
10
Outputs: 1000000000

Inputs: 2147483647
2147483647
Outputs: 2147483647
------------------------------------

Now my code will work if compiled on a 36-Bit machine. : )

Only if you extend the macro by log10(2^36)-log10(2^32) lines.

Martin
--
Martin Golding | He who steals my code steals trash.
DoD #0236 | (Twas mine, tis his, and will be slave to thousands.)
A poor old decrepit Pick programmer. Sympathize at:
fo*****@comcast .net Vancouver, WA

[Old Wolf]

Martin Golding wrote:

>
/* This macro calculates the highest power of 10 less than X */
/* X _must be_ 0 and have no leading 0 */

static int powersOfTen[] =
{ 1
, 10
, 100
, 1000
, 10000
, 100000
, 1000000
, 10000000
, 100000000
,1000000000
};

/* Returns the power of 10 with the same number of digits as X */
#define maxPowerOfTen(X ) (powersOfTen[sizeof(#X)-2])

Doesn't work, eg. maxPowerOfTen(U INT_MAX) is always 7 because
#UINT_MAX is "UINT_MAX".

Even if you do the 'trick' :
#define PS(X) PP(X)
#define PP(X) #X
#define maxPowerOfTen(X ) (powersOfTen[sizeof( PS(X) )-2])

it doesn't work because UINT_MAX might be defined as:
#define UINT_MAX 0xFFFFFFFFU
or
#define UINT_MAX (INT_MAX * 2 + 1)
or worse.

[Old Wolf]

Frederick Gotham wrote:

(1) output <= max_value
(2) Log-base-divisor of output is an exact integer.

What you're trying to say is: the greatest power of DIVISOR that
doesn't exceed MAX_VALUE.

Here it is, in all its glory (note: you may need to extend the number
of iterations past 9 depending on what ranges of values you will be
applying):

#define FRED(N,BASE) (1 \
* ( DIV1(N,BASE) ? (BASE) : 1 ) \
* ( DIV2(N,BASE) ? (BASE) : 1 ) \
* ( DIV3(N,BASE) ? (BASE) : 1 ) \
* ( DIV4(N,BASE) ? (BASE) : 1 ) \
* ( DIV5(N,BASE) ? (BASE) : 1 ) \
* ( DIV6(N,BASE) ? (BASE) : 1 ) \
* ( DIV7(N,BASE) ? (BASE) : 1 ) \
* ( DIV8(N,BASE) ? (BASE) : 1 ) \
* ( DIV9(N,BASE) ? (BASE) : 1 ) \
)

#define DIV0(X,Y) ( X )
#define DIV1(X,Y) ( DIV0(X,Y) / (Y) )
#define DIV2(X,Y) ( DIV1(X,Y) / (Y) )
#define DIV3(X,Y) ( DIV2(X,Y) / (Y) )
#define DIV4(X,Y) ( DIV3(X,Y) / (Y) )
#define DIV5(X,Y) ( DIV4(X,Y) / (Y) )
#define DIV6(X,Y) ( DIV5(X,Y) / (Y) )
#define DIV7(X,Y) ( DIV6(X,Y) / (Y) )
#define DIV8(X,Y) ( DIV7(X,Y) / (Y) )
#define DIV9(X,Y) ( DIV8(X,Y) / (Y) )

#include <stdio.h>
#include <limits.h>

int array[ FRED(12, 10) ];

int main(void)
{
printf("%u\n", FRED( UINT_MAX, 10 ));
printf("%u\n", FRED( 1234, 9 ));
return 0;
}