Repository navigation
Expand file tree
/
Copy pathdivide.ts
More file actions
127 lines (106 loc) · 3.26 KB
/
Copy pathdivide.ts
File metadata and controls
127 lines (106 loc) · 3.26 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
import {
compare,
multiplyDigit,
parseNumber,
removeLeadingZeros,
removeLeadingZerosFromResult,
roundResult,
subtractStrings,
} from "./utils";
export function divide(
left: string,
right: string,
precision: number = 20
): string {
// Modified long division algorithm
function longDivision(
dividend: string,
divisor: string,
precision: number
): string {
let result = "";
let remainder = "";
let dividendIndex = 0;
let decimalPointAdded = false;
let decimalPlaces = 0;
// Calculate one more digit than the desired precision
let maxDecimalPlaces = precision + 1;
while (
dividendIndex < dividend.length ||
(decimalPlaces <= maxDecimalPlaces && compare(remainder, "0") !== 0)
) {
if (dividendIndex < dividend.length) {
remainder += dividend[dividendIndex];
dividendIndex++;
} else {
if (!decimalPointAdded) {
result += ".";
decimalPointAdded = true;
}
remainder += "0";
}
remainder = removeLeadingZeros(remainder);
let quotientDigit = "0";
if (compare(remainder, divisor) >= 0) {
// Find the quotient digit using binary search
let low = 0;
let high = 10;
while (low < high) {
let mid = Math.floor((low + high) / 2);
let product = multiplyDigit(divisor, mid.toString());
if (compare(product, remainder) <= 0) {
low = mid + 1;
} else {
high = mid;
}
}
quotientDigit = (low - 1).toString();
let subtractProduct = multiplyDigit(divisor, quotientDigit);
remainder = subtractStrings(remainder, subtractProduct);
}
result += quotientDigit;
// Increase decimalPlaces after the decimal point is added
if (decimalPointAdded) {
decimalPlaces++;
if (decimalPlaces > maxDecimalPlaces) {
break;
}
}
}
// Round the result
result = roundResult(result, precision);
return result || "0";
}
let num1 = parseNumber(left);
let num2 = parseNumber(right);
if (num2.integerPart === "0" && num2.fractionalPart === "") {
throw new Error("Division by zero");
}
// Convert to whole numbers (integer part + fractional part)
let wholeNum1 = num1.integerPart + num1.fractionalPart;
let wholeNum2 = num2.integerPart + num2.fractionalPart;
// Adjust decimal places
let decimalPlacesNum1 = num1.fractionalPart.length;
let decimalPlacesNum2 = num2.fractionalPart.length;
let scale = decimalPlacesNum2 - decimalPlacesNum1;
if (scale > 0) {
wholeNum1 = wholeNum1 + "0".repeat(scale);
} else if (scale < 0) {
wholeNum2 = wholeNum2 + "0".repeat(-scale);
}
// Remove leading zeros
wholeNum1 = removeLeadingZeros(wholeNum1);
wholeNum2 = removeLeadingZeros(wholeNum2);
// Determine the sign of the result
let resultSign = num1.sign * num2.sign;
// Perform division
let quotient = longDivision(wholeNum1, wholeNum2, precision);
// Remove leading zeros from the integer part of the result
quotient = removeLeadingZerosFromResult(quotient);
// Apply the sign to the result
if (resultSign === -1 && quotient !== "0") {
quotient = "-" + quotient;
}
return quotient;
}
export default divide;