By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,929 Members | 1,245 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,929 IT Pros & Developers. It's quick & easy.

Greatest number divisible by Y

P: n/a
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(max,divisor) /* Something */

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

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

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

Frederick Gotham
Jul 1 '06 #1
Share this Question
Share on Google+
21 Replies


P: n/a
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_by_10 == 1000000000


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

Jul 1 '06 #2

P: n/a
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)
Jul 1 '06 #3

P: n/a
Old Wolf posted:


max == 4294967295
max_divisible_by_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
Jul 1 '06 #4

P: n/a
Frederick Gotham wrote:
> Old Wolf posted:

>>> max == 4294967295
max_divisible_by_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.
Jul 1 '06 #5

P: n/a

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"?

Jul 2 '06 #6

P: n/a
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 UnsignedNumericTypeInfo {
public:

static T const max_power_of_ten = 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 UnsignedNumericTypeInfo {};

template<>
class UnsignedNumericTypeInfo<uint32>
{
static uint32 const max_power_of_ten = 1000000000;
};

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

Frederick Gotham
Jul 2 '06 #7

P: n/a
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 UnsignedNumericTypeInfo {
public:

static T const max_power_of_ten = 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_mindivisor(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,INT_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

Jul 2 '06 #8

P: n/a
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(UINT_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.

Jul 3 '06 #9

P: n/a
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;
}

Jul 3 '06 #10

P: n/a
Frederick Gotham wrote:
[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 UnsignedNumericTypeInfo {
public:

static T const max_power_of_ten = maxPowerOf( (T)-1, 10 );
};
You should ask in a C++ group, unless you have a specific reason to
limit yourself to the common subset of C and C++. In C, you can't do
this without an explicit limit on the supported range. In C++, you can.

Jul 3 '06 #11

P: n/a
Frederick Gotham wrote:
...
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
This can't be done for arbitrary max_value. It's akin to finding the
top most bit of a binary number. [Finding that is easy if you
assume a maximum width, but for arbitrary width integers,
there is no (C language) compile time constant solution, AFAIK.]

You've stated the problems with your intended solution, but you
haven't stated the actual problem. Why do you need a compile
time constant for this?

Assuming your base n is positive...

unsigned long foo(unsigned long max, int n)
{
unsigned long b = n;
while (b <= max / n) b *= n;
return b;
}

--
Peter

Jul 3 '06 #12

P: n/a
=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:
>template<class T>
class UnsignedNumericTypeInfo {
public:

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

You should ask in a C++ group, unless you have a specific reason to
limit yourself to the common subset of C and C++. In C, you can't do
this without an explicit limit on the supported range. In C++, you can.

(Sorry if I quoted your name wrongly, it comes out as garbage on my
system.)

People over on comp.lang.c++ are too busy dealing with high-high-high-high-
higher level stuff; I prefer comp.lang.c for discussion of this nature.
--

Frederick Gotham
Jul 3 '06 #13

P: n/a
Peter Nilsson posted:

This can't be done for arbitrary max_value. It's akin to finding the
top most bit of a binary number.

unsigned guinea_pig = -1;

guinea_pig >>= 1;

guinea_pig = ~guinea_pig;
/* Now you need a compile-time Log-base-2 function, and one has
been posted recently. */
(Just in case anyone's interested, someone recently posted a template
metaprogramming technique for this over on comp.lang.c++.)

Why do you need a compile
time constant for this?

The length of an array is based upon it.

--

Frederick Gotham
Jul 3 '06 #14

P: n/a
Frederick Gotham wrote:
=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:
template<class T>
class UnsignedNumericTypeInfo {
public:

static T const max_power_of_ten = maxPowerOf( (T)-1, 10 );
};
You should ask in a C++ group, unless you have a specific reason to
limit yourself to the common subset of C and C++. In C, you can't do
this without an explicit limit on the supported range. In C++, you can.


(Sorry if I quoted your name wrongly, it comes out as garbage on my system.)
Interesting. Others don't seem to be having this problem replying to
Harold...

Jul 3 '06 #15

P: n/a
Old Wolf posted:
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.

Exactly.

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):
<snip>

Thank you, I'll experiment with it.
--

Frederick Gotham
Jul 3 '06 #16

P: n/a
Frederick Gotham posted:

unsigned guinea_pig = -1;

guinea_pig >>= 1;

guinea_pig = ~guinea_pig;
/* Now you need a compile-time Log-base-2 function, and one has
been posted recently. */


What was I thinking?!
#define MSBOnly(Type) ( ~( (Type)-1 >1 ) )
#define LogBase2(x) /* Something */
#define ValueOfMSB(Type) ( LogBase2( MSBOnly(Type) ) )
int main(void)
{
int array[ ValueOfMSB(unsigned char) ];
}
--

Frederick Gotham
Jul 3 '06 #17

P: n/a
Frederick Gotham wrote:
Peter Nilsson posted:
This can't be done for arbitrary max_value. It's akin to finding the
top most bit of a binary number.

unsigned guinea_pig = -1;
guinea_pig >>= 1;
guinea_pig = ~guinea_pig;
I didn't say the top most bit of an integer _type_. I'm talking about
top most
value bit with value 1 for an _arbitrary_ binary number.

<snip>
Why do you need a compile
time constant for this?

The length of an array is based upon it.
So why does the length of an array need to be known at compile time?

--
Peter

Jul 6 '06 #18

P: n/a
"Peter Nilsson" <ai***@acay.com.auwrites:
Frederick Gotham wrote:
>Peter Nilsson posted:
[snip]
Why do you need a compile
time constant for this?

The length of an array is based upon it.

So why does the length of an array need to be known at compile time?
Perhaps he's using a compiler that doesn't support VLAs.

--
Keith Thompson (The_Other_Keith) 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.
Jul 6 '06 #19

P: n/a
Peter Nilsson posted:
Frederick Gotham wrote:
>Peter Nilsson posted:
This can't be done for arbitrary max_value. It's akin to finding the
top most bit of a binary number.

unsigned guinea_pig = -1;
guinea_pig >>= 1;
guinea_pig = ~guinea_pig;

I didn't say the top most bit of an integer _type_. I'm talking about
top most
value bit with value 1 for an _arbitrary_ binary number.

It would take quite a bit of thought if you had to use macros.

Why do you need a compile
time constant for this?

The length of an array is based upon it.

So why does the length of an array need to be known at compile time?

Strictly speaking, it doesn't, but I'm writing code which I intend to be
ultra-efficient, and so I want to keep dynamic memory allocation to a
minimum (I've none so far).

--

Frederick Gotham
Jul 6 '06 #20

P: n/a
Peter Nilsson writes:
>Frederick Gotham wrote:
>>Peter Nilsson posted:
>>This can't be done for arbitrary max_value. It's akin to
finding the top most bit of a binary number.

unsigned guinea_pig = -1;
guinea_pig >>= 1;
guinea_pig = ~guinea_pig;

I didn't say the top most bit of an integer _type_. I'm talking about
top most value bit with value 1 for an _arbitrary_ binary number.
You can do it up to a chosen limit though. I posted some compile-
time floor(log2()) variants for up to 512 bits in article
<hb**************@bombur.uio.no(thread Value Bits Vs Object Bits),
with similar algorithms to the log10()s needed in this thread.

--
Hallvard
Jul 6 '06 #21

P: n/a
On 2 Jul 2006 19:35:29 -0700, "Old Wolf" <ol*****@inspire.net.nz>
wrote:
Martin Golding wrote:

/* This macro calculates the highest power of 10 less than X */
/* X _must be_ 0 and have no leading 0 */
Must be a single constant/literal, decimal (which in C automatically
means no leading* zero), integer (no decimal point or fractional
digits or exponent). (And no sign not even redundant plus.)

(* For the usual arithmetic meaning of 'leading', i.e. redundant, not
the stringwise meaning of contiguous to beginning. The number zero has
a single digit zero which is at the beginning but not redundant.)
static int powersOfTen[] =
{ 1
, 10
, 100
, 1000
, 10000
, 100000
, 1000000
, 10000000
, 100000000
,1000000000
};
Requires 32-bit (or at least 30-bit) int. long would be safer.
/* 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(UINT_MAX) is always 7 because
#UINT_MAX is "UINT_MAX".

Even if you [indirect] might be [hex, etc.]
And even with these fixes(?) it doesn't produce something the C++
compiler considers a constant = compile-time expression, which is what
the PP wanted. (In C++ unlike C, a const int or enum (scalar)
initialized with a constant expression can be used, but still not an
array. Or for that matter function call, even if available and pure.)

- David.Thompson1 at worldnet.att.net
Jul 10 '06 #22

This discussion thread is closed

Replies have been disabled for this discussion.