440,929 Members | 1,245 Online 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
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 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 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 UnsignedNumericTypeInfo {}; template<> class UnsignedNumericTypeInfo { static uint32 const max_power_of_ten = 1000000000; }; template<> class UnsignedNumericTypeInfo { 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 waskinda 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 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 #include /* 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 #include /* 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 #include 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 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: >templateclass 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 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): 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. 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" 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 San Diego Supercomputer Center <* 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 tofinding 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

 P: n/a On 2 Jul 2006 19:35:29 -0700, "Old Wolf" 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. 