helpers.cpp

/**
 * Boost Software License - Version 1.0 - August 17th, 2003
 * Permission is hereby granted, free of charge, to any person
 * or organization obtaining a copy of the software and
 * accompanying documentation covered by this license
 * (the "Software") to use, reproduce, display, distribute,
 * execute, and transmit the Software, and to prepare derivative
 * works of the Software, and to permit third-parties to whom the
 * Software is furnished to do so, all subject to the following:
 *
 * The copyright notices in the Software and this entire statement,
 * including the above license grant, this restriction and the following
 * disclaimer, must be included in all copies of the Software, in whole or
 * in part, and all derivative works of the Software, unless such copies
 * or derivative works are solely in the form of machine-executable
 * object code generated by a source language processor.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, TITLE AND
 * NON-INFRINGEMENT. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR ANYONE
 * DISTRIBUTING THE SOFTWARE BE LIABLE FOR ANY DAMAGES OR OTHER LIABILITY,
 * WHETHER IN CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#include <istream>
#include <ostream>
#include <bigint.hpp>
#include <algorithm>
#include <vector>
#include <complex>

namespace libbig
{
    int char_int_converter(const char &x) {
        return ((x >= '0' && x <= '9') ? x - '0' : x + '0') ;
    }

    complexCoeffs fast_fourier_transform(const bool is_IDFT, const complexCoeffs num) {

        const int len = num.size();
        const int half_len = len/2;
        const double phase_angle = (is_IDFT) ? (-PI/half_len):(PI/half_len);
        if(len == 1) {
            return num;
        }
        std::complex<double> w_n (1.0, phase_angle);
        std::complex<double> w (1, 0);
        complexCoeffs even_coeffs;
        complexCoeffs odd_coeffs;
        for (int i = 0; i<num.size(); ++i) {
            if(i%2) {
                even_coeffs.push_back(num[i]);
            }
            else {
                odd_coeffs.push_back(num[i]);
            }
            
        }
        even_coeffs = fast_fourier_transform(is_IDFT, even_coeffs);
        odd_coeffs = fast_fourier_transform(is_IDFT, odd_coeffs);
        complexCoeffs Answer;
        Answer.assign(len, 0.0);
        for(int i = 0; i<half_len; ++i) {
            Answer[i] = even_coeffs[i] + w * odd_coeffs[i];
            Answer[half_len + i] = even_coeffs[i] - w * odd_coeffs[i];
            if(is_IDFT) {
                Answer[i] /= len;
                Answer[half_len + i] /= len;
            }
            w *= w_n;
        }
        return Answer;
    }
} // namespace libbig