Thursday, February 9, 2012

Algorithm: Convert large integer from any base to any base.


// Written by Kevin C. Wong
// @JEngineTeam 2/9/2012


// 2-64 Base conversion: from any to any.
// You can increase the base more than 64 by appending m
// ore various characters to the lookup string


#include <iostream>
#include <vector>


#define rep(i,a,b) for(int i=a;i<=b;i++)
#define drep(i,a,b) for(int i=a;i>=b;i--)


using namespace std;


string lookup="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz@_";


string convert(string s,int x, int y)
{
    if(x<=1||x>64)return "error";
    if(y<=1||y>64)return "error";
    if(s.compare("0")==0)return"0";
    int l=s.length();
    if(l==0)return"";    
    int ca=(int)lookup.find(s[l-1]);
    string b=convert(s.substr(0,l-1),x,y);
    int i=b.length()-1;
    
    string t;
    while(i>=0||ca>0)
    {
        int v=ca;
        if(i>=0)
        {
            v+=lookup.find(b.at(i))*x;
        }
        t=lookup[v%y]+t;
        ca=(int)(v/y);
        i--;
    }
  return t;   
}


int main(int argc, char** arg)
{
    cout<<convert("1A5A7A902342734022348904583904829045760724907593",12,12)<<endl;
    cout<<convert("1A5A7A902342734022348904583904829045760724907593",12,5)<<endl;
    cout<<convert("4312311240132203424023310434144444444224420004343440124243024330432321104",5,5)<<endl;
    cout<<convert("4312311240132203424023310434144444444224420004343440124243024330432321104",5,12)<<endl;
    cout<<convert("1",7,19)<<endl;
    cout<<convert("2",10,2)<<endl;
    cout<<convert("0000000",7,19)<<endl;
    cout<<convert("5",7,1)<<endl;
    return 0;
}

No comments:

Post a Comment