Skip to content

Instantly share code, notes, and snippets.

@sentenzo
Last active November 16, 2015 10:53
Show Gist options
  • Save sentenzo/f5c187d82d87b36a6f50 to your computer and use it in GitHub Desktop.
Save sentenzo/f5c187d82d87b36a6f50 to your computer and use it in GitHub Desktop.
Rational number conversion to non decimal base
package com.company;
import java.util.Scanner;
import java.util.HashMap;
public class Main {
// / n \
// | --- |
// \ d /(b)
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt(); // numerator
int d = s.nextInt(); // denominator
int b = s.nextInt(); // base
int i_num = n / d; // integer part
int f_num = n % d;
int f_den = d;
Base e = new Base(b);
String si = e.integer_base_convert(i_num);
String sf = e.fractional_base_convert(f_num, f_den);
System.out.println(si + "." + sf);
}
}
class Base {
// digits alphabet
private static final String[] abc = {
"0", "1", "2", "3", "4"
, "5", "6", "7", "8", "9"
, "a", "b", "c", "d", "e"
, "f", "g", "h", "i", "j"
, "k", "l", "m", "n", "o"
, "p", "q", "r", "s", "t"
, "u", "v", "w", "x", "y"
, "z"
};
private int base;
public Base(int b) {
if (b > abc.length)
throw new Error("Only bases up to "
+ abc.length + " are supported");
base = b;
}
public String integer_base_convert(int x) {
StringBuilder ret = new StringBuilder();
if (x == 0)
return abc[0];
while (x > 0) {
ret.append(abc[x % base]);
x /= base;
}
ret.reverse();
return ret.toString();
}
//
// let's find 5/12 in binary base
// -------+
// |
// +-> 10/12 20/12 16/12 8/12 | 16/12 <-- we've already met "16" before
// | | so, we found the period
// 5 | 10 8 4 8| 4 answer: 0.01(10)
// --*2= 0 + --*2= 1 + --*2= 1 + --*2= 0 + --*2= 1 + --*2=...
// 12 | 12 | 12 | 12 | 12| | 12
// v v v v | v
// 0 . 0 1 ( 1 0 ) | 1
// |
// -------+
//
public String fractional_base_convert(int n, int d) {
StringBuilder ret = new StringBuilder();
int sch = 0;
if (n >= d)
n = n % d;
if (n == 0)
return abc[0];
// state memory to search for periods
HashMap<Integer, Integer> memory = new HashMap<>();
while (true) {
n *= base;
if (memory.containsKey(n)) {
int v = memory.get(n);
// excluding cases like this: 54.321(0)
if (sch - v <= 1 &&
ret.substring(ret.length()-1)
.equals(abc[0])) {
ret.setLength(ret.length() - 1);
break;
}
// 0.33333... => 0.(3)
ret.append(")");
ret.insert(v, "(");
break;
}
memory.put(n, sch++);
ret.append(abc[n / d]);
n %= d;
}
return ret.toString();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment