using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace numtst
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(Format(3.343e100, 0.05)); // 33 followed by 99 zeroes
Console.WriteLine(Format(12.3456, 0.05)); // 12
Console.WriteLine(Format(12.3456, 0.02)); // 12 and 1/3rd
Console.WriteLine(Format(12.3456, 0.0005)); // 12.35
Console.WriteLine(Format(12.3456, 0.0001)); // 12.346
Console.WriteLine(Format(3.343e10, 0.05)); // 33 billion
Console.WriteLine(Format(3.343e10, 0.01)); // 33 and 3/7ths billion
Console.WriteLine(Format(3.343e15, 0.01)); // 3 and 1/3rd million billion
Console.WriteLine(Format(3.343e15, 0.001)); // 3.34 million billion
Console.WriteLine(Format(3.343e15, 0.0001)); // 3.343 million billion
Console.ReadKey();
}
// This is the heart of our algorithm.
static string Format(double num, double prefMaxError)
{
double absNum = Math.Abs(num);
if (absNum < 0.00001) return "0";
// We try a lot of things.
List<FormatResult> list = new List<FormatResult>();
FixedPoint0(absNum, list, 100);
Fraction(absNum, list, 200);
FixedPoint0Postfix(absNum, list, 230);
FractionPostfix(absNum, list, 240);
FixedPoint1Postfix(absNum, list, 250);
FixedPoint2Postfix(absNum, list, 260);
FixedPoint3Postfix(absNum, list, 270);
FixedPoint1(absNum, list, 300);
FixedPoint2(absNum, list, 400);
FixedPoint3(absNum, list, 500);
FollowedByZeroes(absNum, list, 0, 550);
FollowedByZeroes(absNum, list, 1, 600);
FollowedByZeroes(absNum, list, 2, 700);
FollowedByZeroes(absNum, list, 3, 800);
FollowedByZeroes(absNum, list, 4, 800);
// Off-by-one not yet implimented...
// Testing for nice postfix fractions like "1/3rd million" not implemented...
// Billionths and billionths of billionths not implemented.
// If we couldn't find any acceptable representation give up.
if (list.Count == 0)
return "Non-representable number.";
list.Sort(delegate(FormatResult a, FormatResult b)
{
return a.Priority.CompareTo(b.Priority);
});
// We select the best priority item that meets our relative error.
foreach (FormatResult fr in list)
{
double relError = Math.Abs((fr.ActualValue - absNum) / fr.ActualValue);
if (relError < prefMaxError)
return Finalize(num, fr);
}
// Nothing found still... Return the most accurate instead.
list.Sort(delegate(FormatResult a, FormatResult b)
{
double relErrorA = Math.Abs((a.ActualValue - absNum) / a.ActualValue);
double relErrorB = Math.Abs((b.ActualValue - absNum) / b.ActualValue);
if (relErrorA == relErrorB)
return a.Priority.CompareTo(b.Priority);
return relErrorA.CompareTo(relErrorB);
});
return Finalize(num, list[0]);
}
class FormatResult
{
public double ActualValue;
public string Representation;
public bool WrittenNegative;
public int Priority;
public FormatResult(double av, string rep, bool wn, int pr)
{
ActualValue = av;
Representation = rep;
WrittenNegative = wn;
Priority = pr;
}
}
// Brute forces most accurate simple fraction
static string FractionCore(double num, out double outActual, out bool negType)
{
outActual = 0;
negType = false;
// We consider integer parts greater than this value
// not needing of fractional parts.
int maxThreshold = 1000;
if (num >= maxThreshold) return null;
// Brute force
double bestDiff = 10;
int bestD = -1;
int bestN = 0;
for (int denom = 2; denom <= 10; denom++)
{
int n = (int)Math.Round(num * denom);
double actual = n / (double)denom;
double diff = Math.Abs(actual - num);
if (diff < bestDiff)
{
bestDiff = diff;
bestD = denom;
bestN = n;
}
}
if (bestD < 0) return null;
// Make a string out of the best result.
int bestInt = bestN / bestD;
int bestNum = bestN % bestD;
int bestDen = bestD;
if (bestInt >= maxThreshold) return null;
string rep = "";
if (bestInt > 0)
{
rep += bestInt.ToString();
if (bestNum > 0)
rep += " and ";
}
if (bestNum > 0)
{
rep += bestNum.ToString();
rep += "/";
rep += bestDen.ToString();
if (bestDen == 2) ;
else if (bestDen == 3) rep += "rd";
else rep += "th";
if (bestDen != 2 && bestNum > 1) rep += "s";
}
if (bestInt == 0 && bestNum == 0) rep = "0";
double bestActual = (double)bestN / bestD;
outActual = bestActual;
negType = bestInt > 0 && bestNum > 0;
return rep;
}
static void Fraction(double num, List<FormatResult> list, int priority)
{
bool negType;
double actual;
string r = FractionCore(num, out actual, out negType);
if (r == null) return;
list.Add(new FormatResult(actual, r, negType, priority));
}
static void FixedPoint0(double num, List<FormatResult> list, int priority)
{
int maxThreshold = 1000000;
if (num > maxThreshold) num = maxThreshold;
int actual = (int)Math.Round(num);
string rep = string.Format("{0:#,0}", actual);
list.Add(new FormatResult(actual, rep, false, priority));
}
static void FixedPoint1(double num, List<FormatResult> list, int priority)
{
int maxThreshold = 1000000;
if (num > maxThreshold) num = maxThreshold;
int actual = (int)Math.Round(num, 1);
string rep = string.Format("{0:#,0.0}", actual);
list.Add(new FormatResult(actual, rep, false, priority));
}
static void FixedPoint2(double num, List<FormatResult> list, int priority)
{
int maxThreshold = 1000000;
if (num > maxThreshold) num = maxThreshold;
int actual = (int)Math.Round(num, 2);
string rep = string.Format("{0:#,0.00}", actual);
list.Add(new FormatResult(actual, rep, false, priority));
}
static void FixedPoint3(double num, List<FormatResult> list, int priority)
{
int maxThreshold = 1000000;
if (num > maxThreshold) num = maxThreshold;
int actual = (int)Math.Round(num, 3);
string rep = string.Format("{0:#,0.000}", actual);
list.Add(new FormatResult(actual, rep, false, priority));
}
static string PreprocessPostfix(double num, out double start, out double outMult)
{
start = 0;
outMult = 1;
int maxPostfixes = 3;
int numBillions = 0;
bool million = false;
bool thousand = false;
int numPostfixes = 0;
double mult = 1;
while (num > 1000000000 * mult)
{
numPostfixes++;
numBillions++;
mult *= 1000000000;
}
if (num > 1000000 * mult)
{
numPostfixes++;
million = true;
mult *= 1000000;
}
if (num > 1000 * mult)
{
numPostfixes++;
thousand = true;
mult *= 1000;
}
num /= mult;
if (numPostfixes > maxPostfixes) return null;
start = num;
outMult = mult;
string res = "";
if (thousand) res += " thousand";
if (million) res += " million";
for (int i = 0; i < numBillions; i++) res += " billion";
return res;
}
static void FractionPostfix(double num, List<FormatResult> list, int priority)
{
double mult;
string postfix = PreprocessPostfix(num, out num, out mult);
if (postfix == null) return;
double actual;
bool negType;
string rep = FractionCore(num, out actual, out negType) + postfix;
if (rep == null) return;
list.Add(new FormatResult(actual * mult, rep, true, priority));
}
static void FixedPoint0Postfix(double num, List<FormatResult> list, int priority)
{
double mult;
string postfix = PreprocessPostfix(num, out num, out mult);
if (postfix == null) return;
string rep = string.Format("{0:#,0}", num) + postfix;
num = Math.Round(num);
list.Add(new FormatResult(num * mult, rep, true, priority));
}
static void FixedPoint1Postfix(double num, List<FormatResult> list, int priority)
{
double mult;
string postfix = PreprocessPostfix(num, out num, out mult);
if (postfix == null) return;
string rep = string.Format("{0:#,0.0}", num) + postfix;
num = Math.Round(num, 1);
list.Add(new FormatResult(num * mult, rep, true, priority));
}
static void FixedPoint2Postfix(double num, List<FormatResult> list, int priority)
{
double mult;
string postfix = PreprocessPostfix(num, out num, out mult);
if (postfix == null) return;
string rep = string.Format("{0:#,0.00}", num) + postfix;
num = Math.Round(num, 2);
list.Add(new FormatResult(num * mult, rep, true, priority));
}
static void FixedPoint3Postfix(double num, List<FormatResult> list, int priority)
{
double mult;
string postfix = PreprocessPostfix(num, out num, out mult);
if (postfix == null) return;
string rep = string.Format("{0:#,0.000}", num) + postfix;
num = Math.Round(num, 3);
list.Add(new FormatResult(num * mult, rep, true, priority));
}
static void FollowedByZeroes(double num, List<FormatResult> list, int numDigits, int priority)
{
if (num < 1) return;
int numZeroes = (int)Math.Log10(num);
if (numZeroes < numDigits) return;
double mult = Math.Pow(10.0, numZeroes - numDigits);
num /= mult;
int digits = (int)Math.Round(num);
string rep = string.Format("{0:#,0}", digits);
int nz = numZeroes - numDigits;
rep += " followed by " + nz.ToString();
if (nz == 1)
rep += " zero";
else
rep += " zeroes";
double actual = digits * mult;
list.Add(new FormatResult(actual, rep, false, priority));
}
static string Finalize(double num, FormatResult fr)
{
if (num >= 0) return fr.Representation;
if (fr.WrittenNegative)
return "negative " + fr.Representation;
return "-" + fr.Representation;
}
}
}