Warm tip: This article is reproduced from serverfault.com, please click
algorithm math multiplication time-complexity

Egyptian multiplication algorithm complexity?

发布于 2020-11-29 00:54:09

I do understand the algorithm but can't find a way to define its complexity, the only thing i know is it have something to with the second parameter, because if it was smaller the steps will be fewer. Do you have any idea how can i do this? and is there any general way to define time complexity for any given algorithm?

egyptian multiplication algorithm:

def egMul(x, y):
res = 0
while(y>0):
    if(y%2==0):
        x = x * 2
        y = y / 2
    else:
        y = y - 1
        res = res + x
return res
Questioner
Aymane Hrouch
Viewed
0
分享
Paul Hankin 2020-11-29 15:24:26

This code performs Theta(log(y)) arithmetic operations. By considering the binary representation of y, you can see it performs the else branch for each 1 that appears in the binary representation, and it performs the first branch of the if (the one that divides y by 2) floor(log_2(y)) times.

热门帖子

1
今天碰到的一个看似简单的算法问题卡的我头疼：余额和构成余额的交易的问题，问 GPT 也没结果
2
IPV6 太香了
3
最近同事的一句话让我一直耿耿于怀，大伙帮忙分析下
4
最便宜 2.5G 的 Wi-Fi6 光猫， F7615TV3 很不错
5
32 了失业好久，活不下去了，求一份远程工作，前端或者 nextjs 全栈
6
阿里 ECS 突然 CPU 和磁盘 IO 跑满，如何去查，给阿里提工单有用吗
7
公司下个月要裁员，现在要提桶跑路吗？
8
我这个到底是什么病，还有救吗
9
校园网限速，之前用 UDP 协议经过 53 端口可以跑满 500 兆，现在不行了，速度只有几 K，请问如何破。
10
有出服务器类发票的吗？

热门github

1
Implementation of paper - YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information
2
A Windows and Office activator using HWID / Ohook / KMS38 / Online KMS activation methods, with a focus on open-source code and fewer antivirus detections.
3
Get up and running with Llama 2, Mistral, Gemma, and other large language models.
4
该项目可以让你通过订阅的方式使用Cloudflare WARP+，自动获取流量。This project enables you to use Cloudflare WARP+ through subscription, automatically acquiring traffic.
5
Multi functional app to find duplicates, empty folders, similar images etc.
6
Xray panel supporting multi-protocol multi-user expire day & traffic & ip limit (Vmess & Vless & Trojan & ShadowSocks & Wireguard)
7
The Free Software Media System
8
lightweight, standalone C++ inference engine for Google's Gemma models.
9
📚 Freely available programming books
10
A collective list of free APIs
11
1️⃣🐝🏎️ The One Billion Row Challenge -- A fun exploration of how quickly 1B rows from a text file can be aggregated with Java
12
🎓 Path to a free self-taught education in Computer Science!
13
Curso para aprender el lenguaje de programación Python desde cero y para principiantes. 75 clases, 37 horas en vídeo, código, proyectos y grupo de chat. Fundamentos, frontend, backend, testing, IA...
14
This repository contains System Design resources which are useful while preparing for interviews and learning Distributed Systems
15
Mamba is a new state space model architecture showing promising performance on information-dense data such as language modeling, where previous subquadratic models fall short of Transformers. It is based on the line of progress on structured state space models, with an efficient hardware-aware design and implementation in the spirit of FlashAttention.