Java实现floor(n^(1/exp))的正确代码及相关问题咨询

问题背景 #

需要编写Java函数计算floor(n^(1/exp))，其中参数in的取值范围为[2, 2^60]，exp的取值范围为[2, 60]。现有基于Math.pow的实现存在精度问题，尝试BigDecimal方案也未能解决，现咨询两个核心问题：

1. 如何避免繁琐的测试？这类似经典精度问题的指数版本（如1乘3再除以3结果不一定为1）。
2. 若in的范围扩大至2^90，该如何编写代码？

现有实现及测试结果 #

现有测试代码 #

/** @param in input 
  * @param exp exponent >=2 
  * @return floor[in^(1/exp)] */
public static long floorOk1( final long in , final int exp) {  
    final long ret = (long) Math.floor(Math.pow(in,1.0/exp));
    if ( Math.pow(ret+1,exp) <= in ) CORRECTIONS++; // add 1 needed 
        return  ( Math.pow(ret+1,exp) <=in ) ? ret+1L: ret ;   
}
// All OK floorBAD(25 ,2)=5 = floorULP(25 ,2)    
// floorULP(125,3)=5 OK ,BUT floorBAD(125,3)=4 (must be 5 as 5^3=125)  
// floorULP(24389,3)=28 and  floorBAD(24389,3)=28  BOTH WRONG (should be 29 as  29^3= 24389 ) 
/**  (24389,3)->28 is WRONG should be 29 ,  BUT ( 125/3)=5 ok */ 
public static long floorULP( final long in , final int exp) { 
    final double val = Math.pow(in,1.0/exp) ;
    return (long) ( Math.floor(val+Math.ulp(val))); 
} 
/** Arguments (125/3) and (24389,3) -> WRONG results: 1 less than expected. */ 
    public static long floorBAD( final long in , final int exp) { return (long) Math.floor(Math.pow(in,1.0/exp)); } 

    /** Args(in,exp)= (125  ,3) ==> floorBAD is wrong but floorULP is OK 
     *  Args(in,exp)= (24389,3) ==> floorBAD is wrong AND  floorULP also WRONG 
     *  NOTE : WE HAVE 5^3= 125 ; 29^3= 24389  **/
    public static void smallDifferenceTest() { 
        System.out.println(" floorOk1(25,2)    =" + floorOk1(25 ,2)   + " == BAD(25   ,2)=" + floorBAD(25 ,2)   + " Ok=" + (floorBAD(25 ,2)==floorOk1(25 ,2)) ) ;
        System.out.println(" floorOk1(25,2)    =" + floorOk1(25 ,2)   + " == ULP(25   ,2)=" + floorULP(25 ,2)   + " Ok=" + (floorULP(25 ,2)==floorOk1(25 ,2)) ) ;

        System.out.println(" floorOk1(125,3)   =" + floorOk1(125,3)   + " != BAD(125  ,3)=" + floorBAD(125,3)   + " Ok=" + (floorBAD(125,3)==floorOk1(125,3)) ) ;
        System.out.println(" floorOk1(125,3)   =" + floorOk1(125,3)   + " == ULP(125  ,3)=" + floorULP(125,3)   + " Ok=" + (floorULP(125,3)==floorOk1(125,3)) ) ;

        System.out.println(" floorOk1(24389,3) =" + floorOk1(24389,3) + " != ULP(24389,3)=" + floorULP(24389,3) + " Ok=" + (floorULP(24389,3)==floorOk1(24389,3)) ) ; ;
        System.out.println(" floorOk1(24389,3) =" + floorOk1(24389,3) + " != BAD(24389,3)=" + floorBAD(24389,3) + " Ok=" + (floorBAD(24389,3)==floorOk1(24389,3)) ) ; ;
    }

测试结果 #

floorOk1(25,2)    =5 == BAD(25   ,2)=5 Ok=true
 floorOk1(25,2)    =5 == ULP(25   ,2)=5 Ok=true
 floorOk1(125,3)   =5 != BAD(125  ,3)=4 Ok=false
 floorOk1(125,3)   =5 == ULP(125  ,3)=5 Ok=true
 floorOk1(24389,3) =29 != ULP(24389,3)=28 Ok=false
 floorOk1(24389,3) =29 != BAD(24389,3)=28 Ok=false

尝试的BigDecimal方案 #

public static long floorDEC( final long in , final int exp) { 
 return new BigDecimal(Math.pow(in,1.0/exp),MathContext.DECIMAL32).longValue();
    } 

问题解决方案 #

1. 避免繁琐测试的核心思路 #

浮点计算的精度误差无法完全避免，但可以通过精确的整数幂验证逻辑修正误差，从而避免依赖大量测试用例。核心逻辑是：

• 先用Math.pow得到一个近似的初始值；
• 用精确的整数乘法计算ret+1的exp次幂，判断是否不大于输入值，若成立则将结果加1；
• 反向验证ret的exp次幂是否超过输入值，若超过则将结果减1。

这种方法不需要覆盖所有边界，只要验证逻辑正确，就能自动修正浮点计算的误差（误差范围通常在±1以内）。

优化后的代码（针对[2,2^60]范围）

public static long floorRoot(long in, int exp) {
    if (in <= 0 || exp < 2) {
        throw new IllegalArgumentException("in必须≥2，exp必须≥2");
    }
    // 初始浮点估算
    long ret = (long) Math.floor(Math.pow(in, 1.0 / exp));
    
    // 向上修正：验证ret+1的exp次幂是否≤in
    while (true) {
        try {
            long power = 1;
            for (int i = 0; i < exp; i++) {
                power = Math.multiplyExact(power, ret + 1);
                if (power > in) {
                    break;
                }
            }
            if (power <= in) {
                ret++;
            } else {
                break;
            }
        } catch (ArithmeticException e) {
            // 溢出说明(ret+1)^exp > in，停止向上修正
            break;
        }
    }
    
    // 向下修正：验证ret的exp次幂是否>in
    while (true) {
        try {
            long power = 1;
            for (int i = 0; i < exp; i++) {
                power = Math.multiplyExact(power, ret);
                if (power > in) {
                    break;
                }
            }
            if (power <= in) {
                break;
            } else {
                ret--;
            }
        } catch (ArithmeticException e) {
            // 溢出说明ret^exp > in，向下修正
            ret--;
        }
    }
    
    return ret;
}

2. 扩大in范围至2^90的实现方案 #

当in达到2^{90时，已超出`long`的存储范围（`long`最大值为2}63-1），必须使用BigInteger来处理大数运算。BigInteger的pow方法支持精确的大数幂运算，完全避免浮点精度问题。

对应代码

import java.math.BigInteger;
import java.math.BigDecimal;
import java.math.MathContext;

public static BigInteger floorRootBig(BigInteger in, int exp) {
    if (in.compareTo(BigInteger.valueOf(2)) < 0 || exp < 2) {
        throw new IllegalArgumentException("in必须≥2，exp必须≥2");
    }
    // 用BigDecimal得到初始近似值，指定足够精度减少修正次数
    BigDecimal decimalIn = new BigDecimal(in);
    BigDecimal rootApprox = decimalIn.pow(1, new MathContext(40));
    BigInteger ret = rootApprox.toBigInteger();
    
    // 向上修正
    while (true) {
        BigInteger next = ret.add(BigInteger.ONE);
        BigInteger power = next.pow(exp);
        if (power.compareTo(in) <= 0) {
            ret = next;
        } else {
            break;
        }
    }
    
    // 向下修正
    while (ret.pow(exp).compareTo(in) > 0) {
        ret = ret.subtract(BigInteger.ONE);
    }
    
    return ret;
}

内容的提问来源于stack exchange，提问作者Jérôme JEAN-CHARLES