00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include "infft.h"
00022
00023 int X(exp2i)(const int a)
00024 {
00025 return (1U << a);
00026 }
00027
00028 int X(log2i)(const int m)
00029 {
00030 int l = 0;
00031 int mm = m;
00032
00033 while (mm > 0)
00034 {
00035 mm = (mm >> 1);
00036 l++;
00037 }
00038 return (l-1);
00039 }
00040
00043 int X(next_power_of_2)(const int N)
00044 {
00045 int n,i,logn;
00046 int N_is_not_power_of_2=0;
00047
00048 if (N == 0)
00049 return 1;
00050 else
00051 {
00052 n = N;
00053 logn = 0;
00054 while (n != 1)
00055 {
00056 if (n%2 == 1)
00057 N_is_not_power_of_2=1;
00058 n = n/2;
00059 logn++;
00060 }
00061
00062 if (!N_is_not_power_of_2)
00063 logn--;
00064
00065 for (i = 0; i <= logn; i++)
00066 n = n*2;
00067
00068 return n;
00069 }
00070 }
00071
00074 void X(next_power_of_2_exp)(const int N, int *N2, int *t)
00075 {
00076 int n,i,logn;
00077 int N_is_not_power_of_2=0;
00078
00079 if (N == 0)
00080 {
00081 *N2 = 1;
00082 *t = 0;
00083 }
00084 else
00085 {
00086 n=N;
00087 logn=0;
00088 while (n != 1)
00089 {
00090 if (n%2 == 1)
00091 {
00092 N_is_not_power_of_2=1;
00093 }
00094 n = n/2;
00095 logn++;
00096 }
00097
00098 if (!N_is_not_power_of_2)
00099 {
00100 logn--;
00101 }
00102
00103 for (i = 0; i <= logn; i++)
00104 {
00105 n = n*2;
00106 }
00107
00108 *N2 = n;
00109 *t = logn+1;
00110 }
00111 }