Is there a faster complex exponent?

Is there any way to more quickly evaluate complex exponentials, i.e:

where Q is a real array? Quick numerical tests show that complex input noticeably slows down MATLAB's exp function.

Several thoughts:

• Some libraries, such as Julia Base, provide a cis/cisoid function that directly evaluates the Euler expansion.
• The GNU C library has sincos function that simultaneously evaluate sine and cosine more quickly than separate calls.
• The Fixed Point Designer has a cordicexp function that seems to be identical to cis, but I don't have this toolbox. No idea how this performs compared to the standard exp function.

[Walter Roberson]

Hmmm, the timing tests are pretty irregular here in MATLAB online.

On my own system, the timings are closer to 0.0003 / 0.0004

format long g

doit();

t1 = 
                  0.001538

t2 = 
                  0.001853

function doit
    N = 100000;
    Q = randn(1,N);
    
    start = tic; z1 = exp(1i*Q); t1 = toc(start);
    start = tic; z2 = cos(Q) + i*sin(Q); t2 = toc(start);
    
    t1
    t2
end

[Daniel Dolan]

Bumping up to 1E8 points, the trig version is 10-20% slower than the complex exponent. However, the former uses separate calls to cosine and sine, so in principle there could be another factor of two improvment with a sincos function.

[Walter Roberson]

On my system, testing with N = 1e8, the times are about 0.31 / 0.49 which is about 1.58 times slower for the seperate operations.

[Bruno Luong]

"However, the former uses separate calls to cosine and sine,"

How do you know cosine and sine are called separately?

[Daniel Dolan]

I suppose it's possible that the JIT compiler detects adjacent trig functions, but my tests suggest that the composite sum takes about twice as long sine or cosine by itself. MATLAB would have to recognize that both trig calls have the exactly the same argument and invoke a combined sincos function, one that they choose not to implement on its own.

[Bruno Luong]

@Daniel Dolan " but my tests suggest that the composite sum takes about twice as long sine or cosine by itself"

Sorry, the test of this code on my PC ad online PC does NOT clearly support your observation

doit

Elapsed time is 0.015501 seconds.
Elapsed time is 0.018355 seconds.
Elapsed time is 0.016236 seconds.
Elapsed time is 0.017445 seconds.
Elapsed time is 0.010417 seconds.

function doit
N = 1000000;
Q = pi*rand(1,N);

tic; z = exp(1i*Q); toc % Elapsed time is 0.003994 seconds.

tic; z = exp(complex(0,Q)); toc % Elapsed time is 0.007032 seconds.

tic
c = cos(Q);
s = sqrt(1-c.*c);
%ss = 2*mod(Q,2*pi)>pi-1;
z = complex(c,s);
toc % Elapsed time is 0.006615 seconds.

tic
c = cos(Q);
s = sin(Q);;
z = complex(c,s);
toc % Elapsed time is 0.007155 seconds.

tic
c = cos(Q);
s = zeros(size(c));
zr = complex(c,s); % wrong result
toc % Elapsed time is 0.005765 seconds. NOT faster than exp(1i*Q)

end

[Walter Roberson]

cos by itself is faster than anything else, as is to be expected.

But the exp() form is faster than the other three forms

format long g

doit

t1 = 
                  0.013853

t2 = 
                  0.018381

t3 = 
                  0.017218

t4 = 
                  0.023812

t5 = 
                  0.011672

ans = 
          1.32686060781058

ans = 
          1.24290767342814

ans = 
           1.7189056522053

ans = 
         0.842561178084169

function doit
N = 1000000;
Q = pi*rand(1,N);

tic; z = exp(1i*Q); t1 = toc;   %warmup

tic; z = exp(1i*Q); t1 = toc

tic; z = exp(complex(0,Q)); t2 = toc

tic
c = cos(Q);
s = sqrt(1-c.*c);
%ss = 2*mod(Q,2*pi)>pi-1;
z = complex(c,s);
t3 = toc

tic
c = cos(Q);
s = sin(Q);;
z = complex(c,s);
t4 = toc

tic
c = cos(Q);
s = zeros(size(c));
zr = complex(c,s); % wrong result
t5 = toc

t2./t1
t3./t1
t4./t1
t5./t1

end

[Bruno Luong]

"cos by itself is faster than anything else, as is to be expected."

Not on my PC (timing in comment next to toc in my code.

And never twice faster on any PC as @Daniel Dolan claims.

My feeling is exp(1i*Q) is pretty much optimized, so asking to find some way to accelerate it has little chance to be possible acheived.

[Walter Roberson]

But... on my system, I get quite different values

t1 = 0.002637121

t2 = 0.005705978

t3 = 0.008435955

t4 = 0.006200915

t5 = 0.005191424

ans = 2.16371489969554

ans = 3.19892602576825

ans = 2.35139570766757

ans = 1.968595297675

[Paul]

FWIW, Simulink offers a sincos and cos + jsin functions (Trigonometric Function), with options for how those functions are computed (Algorithm - Approximation Method). Don't know if the "under the hood" Simulink implementation would offer any performance benefits if brought into Matlab proper.

[Bruno Luong]

But again I'm not convice MATLAB is NOT already do specific acceleration for exp(1i*Q). It is faster than cos alone on my PC and Walter PC as well

Answer 1

[Daniel Dolan]

(It's a little tacky answering my own question, but I wanted to synthesize helpful comments from Walter and Bruno).

The MATLAB exp must be highly optimized for pure imaginary input. The following code:

function doit()

cis(0); % ensure tabulation runs before time testing

L=50;
N=logspace(3,8,L);
N=round(N);
t0=nan(L,1);
t=nan(L,3);

for k=1:L
    Q = 20*pi*(rand(1,N(k))-0.5); % span multiple cycles, including negative values
    start = tic; 
    [~] = exp(1i*Q); 
    t0(k) = toc(start);
    %
    start=tic; 
    [~]=cos(Q)+1i*sin(Q); % explicit cis(Q)
    t(k,1)=toc(start);
    start=tic;
    [~] = cos(Q); % cosine only
    t(k,2) = toc(start);
    start=tic;
    [~]=cis(Q);
    t(k,3)=toc(start);
end

plot(N,t./t0);
set(gca,'XScale','log')
figure(gcf);
xlabel('Iterations');
ylabel('Time ratio');
legend('Explicit','Cosine only','Tabulation');

end

%%
function out=cis(in)

persistent lookup
if isempty(lookup)
    phi=linspace(0,2*pi,1000);
    z=cos(phi)+1i*sin(phi);
    lookup=griddedInterpolant(phi,z);
end

in=rem(in,2*pi);
out=lookup(in);

end

generates this plot on an M1 Mac running 2023b.

Explicit construction of a real cosine and imaginary sine is slower than the builtin exp function, though not as much so as I would have expected. Not sure what the resonances between 1E3 and 1E4 evaluations come from.

A single trig evaluation is always faster than exp on my Mac. Maybe there are hardware-specific optimizations on the PC?

If Q is always real, periodicity makes it pretty easy to build an interpolation table. I thought this might be faster than exp, but that did not pan out. For many iterations, my tabulation nearly matches exp performance.

To conclude, there is no obvious way to beat MATLAB exp(i*Q) performance for real Q. Hypothetically, a compiled function invoking simultaneous sin/cos evaluation might squeeze out a factor of two, but that does not account for complex number management.

Answer 2

[Sulaymon Eshkabilov]

Let's compare two ways e.g.:

Q = linspace(-10, 10, 1e6);
tic;
CQ1 = exp(1i*Q);
T1 =toc

T1 = 0.0145

tic;
CQ2 = cos(Q)+1i*sin(Q);
T2 =toc

T2 = 0.0347

fprintf('Calc time of exp(1i*Q): %f; cos(Q)+i*sin(Q): %f;  \n', [T1, T2])

Calc time of exp(1i*Q): 0.014515; cos(Q)+i*sin(Q): 0.034731;  

[Daniel Dolan]

It's no surprise that two trig evaluations are slower than the complex exponent. The question is whether we can do better than the complex exponent.