Lecture

Common Multiplicand Speedup

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

MATH-489: Number theory II.d - Cryptography

. ...

Description

This lecture discusses the concept of common multiplicand speedup, which involves expressing two multiplications using logical operations with bitwise AND and XOR. The idea is to optimize the multiplication process by efficiently utilizing logical operations. The instructor explains how to perform these operations and provides observations on the resulting speedup. The lecture covers various scenarios and examples to illustrate the concept of common multiplicand speedup.

Instructor

Dimitar Petkov Jetchev

Official source

Related concepts (32)

Bitwise operation

In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor. Most bitwise operations are presented as two-operand instructions where the result replaces one of the input operands. On simple low-cost processors, typically, bitwise operations are substantially faster than division, several times faster than multiplication, and sometimes significantly faster than addition.

Logical connective

In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary connective can be used to join the two atomic formulas and , rendering the complex formula . Common connectives include negation, disjunction, conjunction, implication, and equivalence.

Logical conjunction

In logic, mathematics and linguistics, and () is the truth-functional operator of conjunction or logical conjunction. The logical connective of this operator is typically represented as or or (prefix) or or in which is the most modern and widely used. The and of a set of operands is true if and only if all of its operands are true, i.e., is true if and only if is true and is true. An operand of a conjunction is a conjunct.

Arithmetic logic unit

In computing, an arithmetic logic unit (ALU) is a combinational digital circuit that performs arithmetic and bitwise operations on integer binary numbers. This is in contrast to a floating-point unit (FPU), which operates on floating point numbers. It is a fundamental building block of many types of computing circuits, including the central processing unit (CPU) of computers, FPUs, and graphics processing units (GPUs).

Logical NOR

In Boolean logic, logical NOR or non-disjunction or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form (p NOR q) is true precisely when neither p nor q is true—i.e. when both of p and q are false. It is logically equivalent to and , where the symbol signifies logical negation, signifies OR, and signifies AND. Non-disjunction is usually denoted as or or (prefix) or .

Related lectures (64)

Numbers and Booleans

Introduces numbers and booleans in Python, covering numeric types, arithmetic operations, logical operations, and comparisons.

MIPS ISA: Instruction Classes and Addressing Modes

Explores MIPS ISA instruction classes, memory organization, and addressing modes, including examples and endianness.

Discrete Optimization: Modeling MOOC: Optimization: principles and algorithms - Network and discrete optimization

Covers logical operations and constraints in discrete optimization modeling.

Programming Basics: Variables, Assignments, and Control Structures

Introduces programming basics, focusing on variables, assignments, and conditional statements.

Propositional Logic: Translations and Equivalences