Abstrakt. En variabel kan multipliceras med en given uppsättning fasta punktkonstanter med hjälp av ett multiplikatorblock som uteslutande består av additioner, subtraktioner och skift. Skapandet av en multiplikator block från uppsättningen konstanter är känd som multipel konstant multiplikation (MCM) problem. Att hitta den optimala lösningen, nämligen den med det minsta antalet tillägg och subtraktioner, är känt för att vara NP-komplett. Vi föreslår en ny algoritm för MCM-problemet, som producerar lösningar som kräver upp till 20% mindre tillägg och subtraktioner än den mest kända algoritmen. Samtidigt är vår algoritm, i motsats till den närmaste konkurrerande algoritmen, inte begränsad av de konstanta bitbredderna. Vi presenterar vår algoritm med hjälp av ett enhetligt formellt ramverk för de bästa, grafbaserade MCM-algoritmerna och ger en detaljerad körtidsanalys och experimentell utvärdering. Vi visar att vår algoritm kan hantera problemstorlekar så stora som 100 32-bitars konstanter i en tid som är acceptabel för de flesta applikationer. Implementeringen av den nya algoritmen finns på www.spiral.net.
Att hitta den optimala lösningen, nämligen den med det minsta antalet tillägg och subtraktioner, är känt för att vara NP-fullständig REF.
Multiplierless multiple constant multiplication
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}