Skip to content

Commit b9b6a6d

Browse files
sjrdsjrd
authored
Merge pull request #5204 from sjrd/rt-long-to-double-much-simpler
Branchless algorithm for RuntimeLong.toDouble.
2 parents c614c82 + d24d1c3 commit b9b6a6d

File tree

4 files changed

+231
-197
lines changed

4 files changed

+231
-197
lines changed

‎javalib/src/main/scala/java/lang/Long.scala

Lines changed: 41 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -145,36 +145,44 @@ object Long {
145145

146146
// Must be called only with valid radix
147147
private def toStringImpl(i: scala.Long, radix: Int): String = {
148+
import js.JSNumberOps.enableJSNumberOps
149+
148150
val lo = i.toInt
149151
val hi = (i >>> 32).toInt
150152

151153
if (lo >> 31 == hi) {
152154
// It's a signed int32
153-
import js.JSNumberOps.enableJSNumberOps
154155
lo.toString(radix)
155-
} else if (hi < 0) {
156-
val neg = -i
157-
"-" + toUnsignedStringInternalLarge(neg.toInt, (neg >>> 32).toInt, radix)
156+
} else if (((hi ^ (hi >> 10)) & 0xffe00000) == 0) { // see RuntimeLong.isSignedSafeDouble
157+
// (lo, hi) is small enough to be a Double, so toDouble is exact
158+
i.toDouble.toString(radix)
158159
} else {
159-
toUnsignedStringInternalLarge(lo, hi, radix)
160+
val abs = Math.abs(i)
161+
val s = toUnsignedStringInternalLarge(abs.toInt, (abs >>> 32).toInt, radix)
162+
if (hi < 0) "-" + s else s
160163
}
161164
}
162165

163166
// Must be called only with valid radix
164167
private def toUnsignedStringImpl(i: scala.Long, radix: Int): String = {
168+
import js.JSNumberOps.enableJSNumberOps
169+
165170
val lo = i.toInt
166171
val hi = (i >>> 32).toInt
167172

168173
if (hi == 0) {
169174
// It's an unsigned int32
170-
import js.JSNumberOps.enableJSNumberOps
171175
Integer.toUnsignedDouble(lo).toString(radix)
176+
} else if ((hi & 0xffe00000) == 0) { // see RuntimeLong.isUnsignedSafeDouble
177+
// (lo, hi) is small enough to be a Double, so toDouble is exact
178+
i.toDouble.toString(radix)
172179
} else {
173180
toUnsignedStringInternalLarge(lo, hi, radix)
174181
}
175182
}
176183

177-
// Must be called only with valid radix and with (lo, hi) >= 2^30
184+
// Must be called only with valid radix and with (lo, hi) >= 2^53
185+
@inline // inlined twice: once in toStringImpl and once in toUnsignedStringImpl
178186
private def toUnsignedStringInternalLarge(lo: Int, hi: Int, radix: Int): String = {
179187
import js.JSNumberOps.enableJSNumberOps
180188
import js.JSStringOps.enableJSStringOps
@@ -185,41 +193,36 @@ object Long {
185193
}
186194

187195
val TwoPow32 = (1L << 32).toDouble
188-
val approxNum =
189-
Integer.toUnsignedDouble(hi) * TwoPow32 + Integer.toUnsignedDouble(lo)
190196

191-
if ((hi & 0xffe00000) == 0) { // see RuntimeLong.isUnsignedSafeDouble
192-
// (lo, hi) is small enough to be a Double, so approxNum is exact
193-
approxNum.toString(radix)
194-
} else {
195-
/* See RuntimeLong.toUnsignedString for a proof. Although that proof is
196-
* done in terms of a fixed divisor of 10^9, it generalizes to any
197-
* divisor that statisfies 2^12 < divisor <= 2^30 and
198-
* ULong.MaxValue / divisor < 2^53, which is true for `radixPowLength`.
199-
*/
197+
/* See RuntimeLong.toUnsignedString for a proof. Although that proof is
198+
* done in terms of a fixed divisor of 10^9, it generalizes to any
199+
* divisor that statisfies 2^12 < divisor <= 2^30 and
200+
* ULong.MaxValue / divisor < 2^53, which is true for `radixPowLength`.
201+
*/
200202

201-
val radixInfo = StringRadixInfos(radix)
202-
val divisor = radixInfo.radixPowLength
203-
val divisorInv = radixInfo.radixPowLengthInverse
204-
val paddingZeros = radixInfo.paddingZeros
205-
206-
// initial approximation of the quotient and remainder
207-
var approxQuot = Math.floor(approxNum * divisorInv)
208-
var approxRem = lo - divisor * unsignedSafeDoubleLo(approxQuot)
209-
210-
// correct the approximations
211-
if (approxRem < 0) {
212-
approxQuot -= 1.0
213-
approxRem += divisor
214-
} else if (approxRem >= divisor) {
215-
approxQuot += 1.0
216-
approxRem -= divisor
217-
}
203+
val radixInfo = StringRadixInfos(radix)
204+
val divisor = radixInfo.radixPowLength
205+
val divisorInv = radixInfo.radixPowLengthInverse
206+
val paddingZeros = radixInfo.paddingZeros
218207

219-
// build the result string
220-
val remStr = approxRem.toString(radix)
221-
approxQuot.toString(radix) + paddingZeros.jsSubstring(remStr.length) + remStr
208+
// initial approximation of the quotient and remainder
209+
val approxNum =
210+
Integer.toUnsignedDouble(hi) * TwoPow32 + Integer.toUnsignedDouble(lo)
211+
var approxQuot = Math.floor(approxNum * divisorInv)
212+
var approxRem = lo - divisor * unsignedSafeDoubleLo(approxQuot)
213+
214+
// correct the approximations
215+
if (approxRem < 0) {
216+
approxQuot -= 1.0
217+
approxRem += divisor
218+
} else if (approxRem >= divisor) {
219+
approxQuot += 1.0
220+
approxRem -= divisor
222221
}
222+
223+
// build the result string
224+
val remStr = approxRem.toString(radix)
225+
approxQuot.toString(radix) + paddingZeros.jsSubstring(remStr.length) + remStr
223226
}
224227

225228
def parseLong(s: String, radix: Int): scala.Long = {

0 commit comments

Comments
 (0)