可以在C语言中在编译时计算处理器值的阶乘吗?

huangapple go评论65阅读模式
英文:

Is it possible to compute factorial value of a proprocessor value during compile time in C?

问题

#define num 7  // 用户可以更改这个值
#define size 5040  // 我想要这个值(num的阶乘)在编译时计算出来

int array[size][num];
英文:
#define num 7  \\ user can change this
#define size ????  \\I want this value (factorial of num) to be computed during compile time

int array[size][num];

I want to define array globally, but its size is dependent on preprocessor num's value. So I want the value (factorial of num) to be determined at compile time.

Is it possible? if yes, how?

答案1

得分: 3

在一个单独的 .h 文件中(例如 fc.h:

#if num == 1
#define sum 1
#elif num == 2
#define sum 2
#elif num == 3
#define sum 6
#elif num == 4
#define sum 24
#elif num == 5
#define sum 120
#elif num == 6
#define sum 720
#elif num == 7
#define sum 5040
#elif num == 8
#define sum 40320
#elif num == 9
#define sum 362880
#else
#error 错误的数字
#endif

用法

#define num 7
#include "fc.h";

int array[sum][num];
英文:

In a separate .h file (for example fc.h):

#if num == 1
#define sum 1
#elif num == 2
#define sum 2
#elif num == 3
#define sum 6
#elif num == 4
#define sum 24
#elif num == 5
#define sum 120
#elif num == 6
#define sum 720
#elif num == 7
#define sum 5040
#elif num == 8
#define sum 40320
#elif num == 9
#define sum 362880
#else
#error wrong number
#endif

Usage

#define num 7
#include "fc.h"

int array[sum][num];

答案2

得分: 3

// 我通常会编写一个简短的Shell脚本来预先计算三元表达式的值。
#define FACTORIAL(i) ( \
i == 1 ? 1 : \
i == 2 ? 2 : \
i == 3 ? 6 : \
i == 4 ? 24 : \
i == 5 ? 120 : \
i == 6 ? 720 : \
i == 7 ? 5040 : \
i == 8 ? 40320 : \
i == 9 ? 362880 : \
-1)

int array[FACTORIAL(3)][3];
英文:

I usually write a short shell script to precompute the values for ternary expression.

// $ for i in $(seq 9); do echo "i == $i ? $(($(seq $i|paste -sd'*'))) : \\"; done
#define FACTORIAL(i) ( \
i == 1 ? 1 : \
i == 2 ? 2 : \
i == 3 ? 6 : \
i == 4 ? 24 : \
i == 5 ? 120 : \
i == 6 ? 720 : \
i == 7 ? 5040 : \
i == 8 ? 40320 : \
i == 9 ? 362880 : \
-1)

int array[FACTORIAL(3)][3];

答案3

得分: 2

以下是您要翻译的内容:

You can manually put something like `(x) * (((x)-1)>0?((x)-1):1) * (((x)-2)>0?((x)-2):1) ...` into the macro.
You only need to approach a couple of iterations since factorials grow so fast and largest supported integers are typically only 64-bits wide.

While an expression like shown above may seem complex, for an `x` that is an integer constant expression
(things like `1`, `1+2`, `sizeof(0)*3`), it is guaranteed to generate an integer constant expression, i.e., something 
suitable for initializing static array sizes, bitfields sizes, and case labels).
Moreover, for arguments that are a preprocessor-recognized integer (e.g, `1`, `42u`, `0x1000ull`), the expression is also preprocessor-recognizable,
i.e., suitable as an argument to an `#if` preprocessor conditional.

So how can you get such a macro?

First you need the upper bound for a factorial argument that won't overflow an  unsigned long long (largest guaranteed to be
supported by the preprocessor and C-compiler, typicall 64-bits wide).

That you can get with something like

#include <stdio.h>
unsigned long long factorial(unsigned long long X){ if(X<=1) return 1; return X*factorial(X-1); }
int main(){
    int i=2;
    for(; i<100 && factorial(i-1)<factorial(i); i++){ if(0) printf("%016llx \n", factorial(i)); }
    printf("%d\n", i-1); //22
}

and it is 22 for 64bit unsigned long longs.

Knowing it is 22, you can generate the macro:

 printf("#define FACTORIAL(X) ((X)>22 || (X)<0 ? 0 : (1 ");
 for(int i=0; i<22; i++) printf(" * ((int)+(X)-%d > 0 ? (X)-%dULL : 1)", i, i);
 printf("))\n");

The above prints

#define FACTORIAL(X) ((X)>22 ? 0 : (1  * ((int)+(X)-0 > 0 ? (X)-0ULL : 1) * ((int)+(X)-1 > 0 ? (X)-1ULL : 1) * ((int)+(X)-2 > 0 ? (X)-2ULL : 1) * ((int)+(X)-3 > 0 ? (X)-3ULL : 1) * ((int)+(X)-4 > 0 ? (X)-4ULL : 1) * ((int)+(X)-5 > 0 ? (X)-5ULL : 1) * ((int)+(X)-6 > 0 ? (X)-6ULL : 1) * ((int)+(X)-7 > 0 ? (X)-7ULL : 1) * ((int)+(X)-8 > 0 ? (X)-8ULL : 1) * ((int)+(X)-9 > 0 ? (X)-9ULL : 1) * ((int)+(X)-10 > 0 ? (X)-10ULL : 1) * ((int)+(X)-11 > 0 ? (X)-11ULL : 1) * ((int)+(X)-12 > 0 ? (X)-12ULL : 1) * ((int)+(X)-13 > 0 ? (X)-13ULL : 1) * ((int)+(X)-14 > 0 ? (X)-14ULL : 1) * ((int)+(X)-15 > 0 ? (X)-15ULL : 1) * ((int)+(X)-16 > 0 ? (X)-16ULL : 1) * ((int)+(X)-17 > 0 ? (X)-17ULL : 1) * ((int)+(X)-18 > 0 ? (X)-18ULL : 1) * ((int)+(X)-19 > 0 ? (X)-19ULL : 1) * ((int)+(X)-20 > 0 ? (X)-20ULL : 1) * ((int)+(X)-21 > 0 ? (X)-21ULL : 1)))


and you can test this macro for preprocessor-recognized integers:

#if FACTORIAL(1)!=1 || FACTORIAL(6)!=720 || FACTORIAL(22) != 0xeea4c2b3e0d80000
   #error ""
#endif

and for integer constant-expressions that aren't preprocessor-recognized:


_Static_assert(FACTORIAL(6*sizeof(char))==720,"");
英文:

You can manually put something like (x) * (((x)-1)>0?((x)-1):1) * (((x)-2)>0?((x)-2):1) ... into the macro.
You only need to approach a couple of iterations since factorials grow so fast and largest supported integers are typically only 64-bits wide.

While an expression like shown above may seem complex, for an x that is an integer constant expression
(things like 1, 1+2, sizeof(0)*3), it is guaranteed to generate an integer constant expression, i.e., something
suitable for initializing static array sizes, bitfields sizes, and case labels).
Moreover, for arguments that are a preprocessor-recognized integer (e.g, 1, 42u, 0x1000ull), the expression is also preprocessor-recognizable,
i.e., suitable as an argument to an #if preprocessor conditional.

So how can you get such a macro?

First you need the upper bound for a factorial argument that won't overflow an unsigned long long (largest guaranteed to be
supported by the preprocessor and C-compiler, typicall 64-bits wide).

That you can get with something like

#include <stdio.h>
unsigned long long factorial(unsigned long long X){ if(X<=1) return 1; return X*factorial(X-1); }
int main(){
    int i=2;
    for(; i<100 && factorial(i-1)<factorial(i); i++){ if(0) printf("%016llx \n", factorial(i)); }
    printf("%d\n", i-1); //22
}

and it is 22 for 64bit unsigned long longs.

Knowing it is 22, you can generate the macro:

 printf("#define FACTORIAL(X) ((X)>22 || (X)<0 ? 0 : (1 ");
 for(int i=0; i<22; i++) printf(" * ((int)+(X)-%d > 0 ? (X)-%dULL : 1)", i, i);
 printf("))\n");

The above prints

#define FACTORIAL(X) ((X)>22 ? 0 : (1  * ((int)+(X)-0 > 0 ? (X)-0ULL : 1) * ((int)+(X)-1 > 0 ? (X)-1ULL : 1) * ((int)+(X)-2 > 0 ? (X)-2ULL : 1) * ((int)+(X)-3 > 0 ? (X)-3ULL : 1) * ((int)+(X)-4 > 0 ? (X)-4ULL : 1) * ((int)+(X)-5 > 0 ? (X)-5ULL : 1) * ((int)+(X)-6 > 0 ? (X)-6ULL : 1) * ((int)+(X)-7 > 0 ? (X)-7ULL : 1) * ((int)+(X)-8 > 0 ? (X)-8ULL : 1) * ((int)+(X)-9 > 0 ? (X)-9ULL : 1) * ((int)+(X)-10 > 0 ? (X)-10ULL : 1) * ((int)+(X)-11 > 0 ? (X)-11ULL : 1) * ((int)+(X)-12 > 0 ? (X)-12ULL : 1) * ((int)+(X)-13 > 0 ? (X)-13ULL : 1) * ((int)+(X)-14 > 0 ? (X)-14ULL : 1) * ((int)+(X)-15 > 0 ? (X)-15ULL : 1) * ((int)+(X)-16 > 0 ? (X)-16ULL : 1) * ((int)+(X)-17 > 0 ? (X)-17ULL : 1) * ((int)+(X)-18 > 0 ? (X)-18ULL : 1) * ((int)+(X)-19 > 0 ? (X)-19ULL : 1) * ((int)+(X)-20 > 0 ? (X)-20ULL : 1) * ((int)+(X)-21 > 0 ? (X)-21ULL : 1)))

and you can test this macro for preprocessor-recognized integers:

#if FACTORIAL(1)!=1 || FACTORIAL(6)!=720 || FACTORIAL(22) != 0xeea4c2b3e0d80000
   #error ""
#endif

and for integer constant-expressions that aren't preprocessor-recognized:

_Static_assert(FACTORIAL(6*sizeof(char))==720,"");

答案4

得分: 0

以下是翻译好的部分,代码部分不翻译:

It is possible. As others have pointed out, you can hardcode the values. That being said, you can also take a computational approach. If you are interested in compile-time metaprogramming, I recommend you take a look at Order-pp. Using that library, you can easily implement the factorial function like so:
如果你有兴趣进行编译时元编程,我建议你查看 Order-pp。使用该库,你可以轻松地实现阶乘函数,如下所示:

#define ORDER_PP_DEF_8fac ORDER_PP_FN \
(8fn (8N \
     ,8if (8is_0 (8N) \
          ,1 \
          ,8mul (8N, 8fac (8dec (8N))) \
          ) \
     ) \
)

#define FACTORIAL(n) ORDER_PP (8to_lit (8fac (n)))

FACTORIAL (15) // 15! == 1307674368000

If however you want a more minimalist approach, there's an exploit in gcc that enables macro recursion. It works better for gcc 11 and prior. It also uses a number of gcc extensions, but since the exploit works nowhere else, there is no problem:
然而,如果你想要更简洁的方法,GCC 中有一种启用宏递归的漏洞。它在 GCC 11 及之前的版本中效果更好。它还使用了许多 GCC 扩展,但由于这种漏洞在其他地方不起作用,所以没有问题:

#2""3 // 禁用警告
// 宏复活漏洞
#define PRAGMA(p...) _Pragma(#p)
#define REVIVE(m) PRAGMA(push_macro(#m)) PRAGMA(pop_macro(#m))

// 延迟宏应用
#define FX(f,x) REVIVE(FX) f x

// Church 布尔值
#define IF_(t,f...) REVIVE(IF_) t
#define IF_1(t,f...) REVIVE(IF_1) f

// 是否为零的谓词
#define ZP(...) IF_##__VA_OPT__(1)

// 基于逗号编码的算术
#define DEC(n,ns...) REVIVE(DEC) (ns)
#define INC(ns...) REVIVE(INC) (,ns)

// acc 用于 FACT 内部使用,不应该由用户提供参数
#define FACT(n,acc...) REVIVE(FACT) (ZP n (IF_##__VA_OPT__(1) (1ul, (acc)), __VA_OPT__((acc) *) FX (FACT, (DEC n, acc + 1ul))))

int main () {printf ("%llu", FACT((,,,,, ,,,,, ,,,,,)));} // 15! == 1307674368000

If you choose the latter, here's a bonus function to turn comma encoded numbers into C integer expressions:
如果你选择后一种方法,这里有一个额外的函数,将逗号编码的数字转换为 C 整数表达式:

#define TO_LIT(n...) REVIVE(TO_LIT) ZP(n) (0, 1 + TO_LIT DEC(n))

TO_LIT (,,,,) // (1+ (1+ (1+ (1+ (0))))) == 4

If you want to test modifications of this, use options -E and -P to obtain the preprocessor output.
如果你想测试对此的修改,请使用选项 -E 和 -P 来获取预处理器输出。

英文:

It is possible. As others have pointed out, you can hardcode the values. That being said, you can also take a computational approach. If you are interested in compile-time metaprogramming, I recommend you take a look at Order-pp. Using that library, you can easily implement the factorial function like so:

#define ORDER_PP_DEF_8fac ORDER_PP_FN \
(8fn (8N \
     ,8if (8is_0 (8N) \
          ,1 \
          ,8mul (8N, 8fac (8dec (8N))) \
          ) \
     ) \
)

#define FACTORIAL(n) ORDER_PP (8to_lit (8fac (n)))

FACTORIAL (15) // 15! == 1307674368000

If however you want a more minimalist approach, there's an exploit in gcc that enables macro recursion. It works better for gcc 11 and prior. It also uses a number of gcc extensions, but since the exploit works nowhere else, there is no problem:

#2""3 // disables warnings
// macro revival exploit
#define PRAGMA(p...) _Pragma(#p)
#define REVIVE(m) PRAGMA(push_macro(#m)) PRAGMA(pop_macro(#m))

// deferred macro application
#define FX(f,x) REVIVE(FX) f x

// Church booleans
#define IF_(t,f...) REVIVE(IF_) t
#define IF_1(t,f...) REVIVE(IF_1) f

// is-zero predicate
#define ZP(...) IF_##__VA_OPT__(1)

// base 1 comma encoded arithmetic
#define DEC(n,ns...) REVIVE(DEC) (ns)
#define INC(ns...) REVIVE(INC) (,ns)

// acc is used internally by FACT and should not be given an argument by the user
#define FACT(n,acc...) REVIVE(FACT) (ZP n (IF_##__VA_OPT__(1) (1ul, (acc)), __VA_OPT__((acc) *) FX (FACT, (DEC n, acc + 1ul))))

int main () {printf ("%llu", FACT((,,,,, ,,,,, ,,,,,)));} // 15! == 1307674368000

If you choose the latter, here's a bonus function to turn comma encoded numbers into C integer expressions:

#define TO_LIT(n...) REVIVE(TO_LIT) ZP(n) (0, 1 + TO_LIT DEC(n))

TO_LIT (,,,,) // (1+ (1+ (1+ (1+ (0))))) == 4

If you want to test modifications of this, use options -E and -P to obtain the preprocessor output.

huangapple
  • 本文由 发表于 2023年2月13日 23:32:23
  • 转载请务必保留本文链接:https://go.coder-hub.com/75437987.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定