热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Java实现大数乘法(分治算法)

本文介绍了使用Java实现大数乘法的分治算法,包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。
 
 
java代码(long需要改变)
import java.util.Arrays;
import java.util.Scanner;
public class 大数乘法 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("输入数据:");
        String a = in.nextLine();
        String b = in.nextLine();
        long num1 = temp(a);
        long num2 = temp(b);
        String result1 =  bigNumberMulti(a, b);
        long result2 = karatsubaMulti(num1, num2);
        System.out.println("普通大数乘法的结果:\n"+a+" * "+b+"\n= "+result1);
        System.out.println("Karatsuba大数乘法结果:\n"+a+" * "+b+"\n= "+result2);

    }



    public static String bigNumberMulti(String a, String b){
        //字符串转换成数组
        char[] charArr1 = a.trim().toCharArray();
        char[] charArr2 = b.trim().toCharArray();
        int[] arr1 = new int[charArr1.length];
        int[] arr2 = new int[charArr2.length];
        for (int i = 0; i ) {
            arr1[i] = charArr1[i] - ‘0‘;
        }
        for (int i = 0; i ) {
            arr2[i] = charArr2[i] - ‘0‘;
        }

        //大数乘法(不进位)
        int[] result = new int[arr1.length + arr2.length];
        for (int i = 0; i ) {
            for (int j = 0; j ) {
                result[i+j+1] += arr1[i] * arr2[j];
            }
        }
        //处理进位,result是逆序储存的
        for (int k = result.length - 1; k > 0; k--) {
            if(result[k] >= 10 && k != 1){
                result[k-1] += result[k]/10;
                result[k] %= 10;
            }
        }
        String resultStr = "";
        for (int i = 1; i ) {
            resultStr += ""+result[i];
        }
        return resultStr;
    }
    public static long karatsubaMulti(long num1, long num2 ){
        if(num1 <10 || num2 <10)
            return num1*num2;
        int size1 = String.valueOf(num1).length();
        int size2 = String.valueOf(num2).length();
        int halfSize = Math.max(size1, size2) / 2;

        long a = Long.valueOf(String.valueOf(num1).substring(0, size1 - halfSize));
        long b = Long.valueOf(String.valueOf(num1).substring(size1 - halfSize));
        long c = Long.valueOf(String.valueOf(num2).substring(0, size2 - halfSize));
        long d = Long.valueOf(String.valueOf(num2).substring(size2 - halfSize));

        long x0 = karatsubaMulti(b, d);
        long x2 = karatsubaMulti(a, c);
        long x1 = karatsubaMulti((a+b), (c+d)) - x0 - x2;

        return (long)(x2*Math.pow(10, (2*halfSize)) + x1*Math.pow(10, halfSize) + x0);

    }
    public static long temp(String a){
        long result = 0;
        for (int i = 0; i ) {
            result *= 10;
            result += a.charAt(i) - ‘0‘;
        }
        return result;
    }

}

大数乘法(分治)


推荐阅读
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 本文详细介绍了Java中org.neo4j.helpers.collection.Iterators.single()方法的功能、使用场景及代码示例,帮助开发者更好地理解和应用该方法。 ... [详细]
  • Java 中 Writer flush()方法,示例 ... [详细]
  • Java 中的 BigDecimal pow()方法,示例 ... [详细]
  • Java 类成员初始化顺序与数组创建
    本文探讨了Java中类成员的初始化顺序、静态引入、可变参数以及finalize方法的应用。通过具体的代码示例,详细解释了这些概念及其在实际编程中的使用。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息,以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制,解释其原理及应用场景。 ... [详细]
  • 主要用了2个类来实现的,话不多说,直接看运行结果,然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文介绍了如何使用 Spring Boot DevTools 实现应用程序在开发过程中自动重启。这一特性显著提高了开发效率,特别是在集成开发环境(IDE)中工作时,能够提供快速的反馈循环。默认情况下,DevTools 会监控类路径上的文件变化,并根据需要触发应用重启。 ... [详细]
  • PHP 5.2.5 安装与配置指南
    本文详细介绍了 PHP 5.2.5 的安装和配置步骤,帮助开发者解决常见的环境配置问题,特别是上传图片时遇到的错误。通过本教程,您可以顺利搭建并优化 PHP 运行环境。 ... [详细]
  • 将Web服务部署到Tomcat
    本文介绍了如何在JDeveloper 12c中创建一个Java项目,并将其打包为Web服务,然后部署到Tomcat服务器。内容涵盖从项目创建、编写Web服务代码、配置相关XML文件到最终的本地部署和验证。 ... [详细]
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
  • 深入理解Tornado模板系统
    本文详细介绍了Tornado框架中模板系统的使用方法。Tornado自带的轻量级、高效且灵活的模板语言位于tornado.template模块,支持嵌入Python代码片段,帮助开发者快速构建动态网页。 ... [详细]
  • MySQL中枚举类型的所有可能值获取方法
    本文介绍了一种在MySQL数据库中查询枚举(ENUM)类型字段所有可能取值的方法,帮助开发者更好地理解和利用这一数据类型。 ... [详细]
author-avatar
傅笑寒
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有