/***************************************************************************  **************************************************************************                  Spherical Harmonic Transform Kit 2.7       Contact: Peter Kostelec            geelong@cs.dartmouth.edu       Copyright 1997-2003  Sean Moore, Dennis Healy,                        Dan Rockmore, Peter Kostelec       Copyright 2004  Peter Kostelec, Dan Rockmore     SpharmonicKit is free software; you can redistribute it and/or modify     it under the terms of the GNU General Public License as published by     the Free Software Foundation; either version 2 of the License, or     (at your option) any later version.       SpharmonicKit is distributed in the hope that it will be useful,     but WITHOUT ANY WARRANTY; without even the implied warranty of     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the     GNU General Public License for more details.       You should have received a copy of the GNU General Public License     along with this program; if not, write to the Free Software     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.       Commercial use is absolutely prohibited.     See the accompanying LICENSE file for details.    ************************************************************************  ************************************************************************//* these are the bit-reverse, 4096 roots of unity, and by subrecursion,   contains all Nth roots of unity (N < 4096) in bit-reversed order */const double r4096[8192] ={1.000000000000000, 0, -1.000000000000000, 0, 0,  1.000000000000000, 0, -1.000000000000000,   0.707106781186548, 0.707106781186547, -0.707106781186547,   -0.707106781186548, -0.707106781186547, 0.707106781186548,   0.707106781186548, -0.707106781186547, 0.923879532511287,   0.382683432365090, -0.923879532511287, -0.382683432365090,   -0.382683432365090, 0.923879532511287, 0.382683432365090,   -0.923879532511287, 0.382683432365090, 0.923879532511287,   -0.382683432365090, -0.923879532511287, -0.923879532511287,   0.382683432365090, 0.923879532511287, -0.382683432365090,   0.980785280403230, 0.1950903220161282, -0.980785280403230,   -0.1950903220161286, -0.1950903220161282, 0.980785280403230,   0.1950903220161283, -0.980785280403230, 0.555570233019602,   0.831469612302545, -0.555570233019602, -0.831469612302545,   -0.831469612302545, 0.555570233019602, 0.831469612302545,   -0.555570233019602, 0.831469612302545, 0.555570233019602,   -0.831469612302545, -0.555570233019602, -0.555570233019602,   0.831469612302545, 0.555570233019602, -0.831469612302545,   0.1950903220161283, 0.980785280403230, -0.1950903220161282,   -0.980785280403230, -0.980785280403230, 0.1950903220161286,   0.980785280403230, -0.1950903220161282, 0.995184726672197,   0.0980171403295606, -0.995184726672197, -0.0980171403295608,   -0.0980171403295607, 0.995184726672197, 0.0980171403295608,   -0.995184726672197, 0.634393284163646, 0.773010453362737,   -0.634393284163645, -0.773010453362737, -0.773010453362737,   0.634393284163645, 0.773010453362737, -0.634393284163645,   0.881921264348355, 0.471396736825998, -0.881921264348355,   -0.471396736825998, -0.471396736825998, 0.881921264348355,   0.471396736825998, -0.881921264348355, 0.290284677254462,   0.956940335732209, -0.290284677254462, -0.956940335732209,   -0.956940335732209, 0.290284677254462, 0.956940335732209,   -0.290284677254462, 0.956940335732209, 0.290284677254462,   -0.956940335732209, -0.290284677254462, -0.290284677254462,   0.956940335732209, 0.290284677254462, -0.956940335732209,   0.471396736825998, 0.881921264348355, -0.471396736825998,   -0.881921264348355, -0.881921264348355, 0.471396736825998,   0.881921264348355, -0.471396736825998, 0.773010453362737,   0.634393284163645, -0.773010453362737, -0.634393284163645,   -0.634393284163645, 0.773010453362737, 0.634393284163646,   -0.773010453362737, 0.0980171403295608, 0.995184726672197,   -0.0980171403295607, -0.995184726672197, -0.995184726672197,   0.0980171403295608, 0.995184726672197, -0.0980171403295606,   0.998795456205172, 0.04906767432741802, -0.998795456205172,   -0.04906767432741798, -0.04906767432741801, 0.998795456205172,   0.04906767432741814, -0.998795456205172, 0.671558954847018,   0.740951125354959, -0.671558954847018, -0.740951125354959,   -0.740951125354959, 0.671558954847019, 0.740951125354959,   -0.671558954847018, 0.903989293123443, 0.427555093430282,   -0.903989293123443, -0.427555093430282, -0.427555093430282,   0.903989293123443, 0.427555093430282, -0.903989293123443,   0.336889853392220, 0.941544065183021, -0.336889853392220,   -0.941544065183021, -0.941544065183021, 0.336889853392220,   0.941544065183021, -0.336889853392220, 0.970031253194544,   0.2429801799032639, -0.970031253194544, -0.242980179903264,   -0.2429801799032639, 0.970031253194544, 0.242980179903264,   -0.970031253194544, 0.514102744193222, 0.857728610000272,   -0.514102744193222, -0.857728610000272, -0.857728610000272,   0.514102744193222, 0.857728610000272, -0.514102744193222,   0.803207531480645, 0.595699304492433, -0.803207531480645,   -0.595699304492433, -0.595699304492433, 0.803207531480645,   0.595699304492433, -0.803207531480645, 0.1467304744553617,   0.989176509964781, -0.1467304744553616, -0.989176509964781,   -0.989176509964781, 0.1467304744553618, 0.989176509964781,   -0.1467304744553617, 0.989176509964781, 0.1467304744553617,   -0.989176509964781, -0.1467304744553618, -0.1467304744553616,   0.989176509964781, 0.1467304744553617, -0.989176509964781,   0.595699304492433, 0.803207531480645, -0.595699304492433,   -0.803207531480645, -0.803207531480645, 0.595699304492433,   0.803207531480645, -0.595699304492433, 0.857728610000272,   0.514102744193222, -0.857728610000272, -0.514102744193222,   -0.514102744193222, 0.857728610000272, 0.514102744193222,   -0.857728610000272, 0.242980179903264, 0.970031253194544,   -0.2429801799032639, -0.970031253194544, -0.970031253194544,   0.242980179903264, 0.970031253194544, -0.2429801799032639,   0.941544065183021, 0.336889853392220, -0.941544065183021,   -0.336889853392220, -0.336889853392220, 0.941544065183021,   0.336889853392220, -0.941544065183021, 0.427555093430282,   0.903989293123443, -0.427555093430282, -0.903989293123443,   -0.903989293123443, 0.427555093430282, 0.903989293123443,   -0.427555093430282, 0.740951125354959, 0.671558954847018,   -0.740951125354959, -0.671558954847019, -0.671558954847018,   0.740951125354959, 0.671558954847018, -0.740951125354959,   0.04906767432741814, 0.998795456205172, -0.04906767432741801,   -0.998795456205172, -0.998795456205172, 0.04906767432741798,   0.998795456205172, -0.04906767432741802, 0.999698818696204,   0.02454122852291229, -0.999698818696204, -0.02454122852291233,   -0.02454122852291214, 0.999698818696204, 0.02454122852291227,   -0.999698818696204, 0.689540544737067, 0.724247082951467,   -0.689540544737067, -0.724247082951467, -0.724247082951467,   0.689540544737067, 0.724247082951467, -0.689540544737067,   0.914209755703531, 0.405241314004990, -0.914209755703531,   -0.405241314004990, -0.405241314004990, 0.914209755703531,   0.405241314004990, -0.914209755703531, 0.359895036534988,   0.932992798834739, -0.359895036534988, -0.932992798834739,   -0.932992798834739, 0.359895036534988, 0.932992798834739,   -0.359895036534988, 0.975702130038529, 0.2191012401568698,   -0.975702130038528, -0.21910124015687, -0.2191012401568697,   0.975702130038529, 0.2191012401568698, -0.975702130038529,   0.534997619887097, 0.844853565249707, -0.534997619887097,   -0.844853565249707, -0.844853565249707, 0.534997619887097,   0.844853565249707, -0.534997619887097, 0.817584813151584,   0.575808191417845, -0.817584813151583, -0.575808191417845,   -0.575808191417845, 0.817584813151584, 0.575808191417845,   -0.817584813151584, 0.1709618887603014, 0.985277642388941,   -0.1709618887603012, -0.985277642388941, -0.985277642388941,   0.1709618887603012, 0.985277642388941, -0.1709618887603012,   0.992479534598710, 0.1224106751992162, -0.992479534598710,   -0.1224106751992164, -0.1224106751992162, 0.992479534598710,   0.1224106751992163, -0.992479534598710, 0.615231590580627,   0.788346427626606, -0.615231590580627, -0.788346427626606,   -0.788346427626606, 0.615231590580627, 0.788346427626606,   -0.615231590580627, 0.870086991108711, 0.492898192229784,   -0.870086991108711, -0.492898192229784, -0.492898192229784,   0.870086991108711, 0.492898192229784, -0.870086991108711,   0.266712757474898, 0.963776065795440, -0.266712757474898,   -0.963776065795440, -0.963776065795440, 0.266712757474898,   0.963776065795440, -0.266712757474898, 0.949528180593037,   0.313681740398892, -0.949528180593037, -0.313681740398891,   -0.313681740398891, 0.949528180593037, 0.313681740398892,   -0.949528180593037, 0.449611329654607, 0.893224301195515,   -0.449611329654607, -0.893224301195515, -0.893224301195515,   0.449611329654607, 0.893224301195515, -0.449611329654607,   0.757208846506485, 0.653172842953777, -0.757208846506485,   -0.653172842953777, -0.653172842953777, 0.757208846506485,   0.653172842953777, -0.757208846506485, 0.07356456359966746,   0.997290456678690, -0.07356456359966735, -0.997290456678690,   -0.997290456678690, 0.07356456359966775, 0.997290456678690,   -0.07356456359966744, 0.997290456678690, 0.07356456359966744,   -0.997290456678690, -0.07356456359966775, -0.07356456359966735,   0.997290456678690, 0.07356456359966746, -0.997290456678690,   0.653172842953777, 0.757208846506485, -0.653172842953777,   -0.757208846506485, -0.757208846506485, 0.653172842953777,   0.757208846506485, -0.653172842953777, 0.893224301195515,   0.449611329654607, -0.893224301195515, -0.449611329654607,   -0.449611329654607, 0.893224301195515, 0.449611329654607,   -0.893224301195515, 0.313681740398892, 0.949528180593037,   -0.313681740398891, -0.949528180593037, -0.949528180593037,   0.313681740398891, 0.949528180593037, -0.313681740398892,   0.963776065795440, 0.266712757474898, -0.963776065795440,   -0.266712757474898, -0.266712757474898, 0.963776065795440,   0.266712757474898, -0.963776065795440, 0.492898192229784,   0.870086991108711, -0.492898192229784, -0.870086991108711,   -0.870086991108711, 0.492898192229784, 0.870086991108711,   -0.492898192229784, 0.788346427626606, 0.615231590580627,   -0.788346427626606, -0.615231590580627, -0.615231590580627,   0.788346427626606, 0.615231590580627, -0.788346427626606,   0.1224106751992163, 0.992479534598710, -0.1224106751992162,   -0.992479534598710, -0.992479534598710, 0.1224106751992164,   0.992479534598710, -0.1224106751992162, 0.985277642388941,   0.1709618887603012, -0.985277642388941, -0.1709618887603012,   -0.1709618887603012, 0.985277642388941, 0.1709618887603014,   -0.985277642388941, 0.575808191417845, 0.817584813151584,   -0.575808191417845, -0.817584813151584, -0.817584813151583,   0.575808191417845, 0.817584813151584, -0.575808191417845,   0.844853565249707, 0.534997619887097, -0.844853565249707,   -0.534997619887097, -0.534997619887097, 0.844853565249707,   0.534997619887097, -0.844853565249707, 0.2191012401568698,   0.975702130038529, -0.2191012401568697, -0.975702130038529,   -0.975702130038528, 0.21910124015687, 0.975702130038529,   -0.2191012401568698, 0.932992798834739, 0.359895036534988,   -0.932992798834739, -0.359895036534988, -0.359895036534988,   0.932992798834739, 0.359895036534988, -0.932992798834739,   0.405241314004990, 0.914209755703531, -0.405241314004990,   -0.914209755703531, -0.914209755703531, 0.405241314004990,   0.914209755703531, -0.405241314004990, 0.724247082951467,   0.689540544737067, -0.724247082951467, -0.689540544737067,   -0.689540544737067, 0.724247082951467, 0.689540544737067,   -0.724247082951467, 0.02454122852291227, 0.999698818696204,   -0.02454122852291214, -0.999698818696204, -0.999698818696204,   0.02454122852291233, 0.999698818696204, -0.02454122852291229,