#include

#include

#include

#include

#include

#define BENCH$\_$LOOPS $10000$

typedef uint$64\_$t bigint$256[16]$; $//$for operands

typedef uint$64\_$t bigint$512[32]$; $//$for multiplication result

const bigint$256$ a$\_$exp $=$

$\{0$x$13$ab$,0$xfdb$2,0$xd$231,0$xc$1$b$3,0$xb$1$d$0,0$x$0867,0$x$14$d$8,0$x$0102,0$x$5$c$99,0$x$380$b$,0$x$658$a$,0$xc$27$

$9,0$x$9$b$97,0$x$02$d$1,0$xda$40,0$x$52$fa$\}$;

const bigint$256$ b$\_$exp $=$

$\{0$x$79$f$5,0$x$5500,0$xda$19,0$xed$75,0$xe$4$a$0,0$x$48$b$6,0$x$695$f$,0$x$0$ee$7,0$x$6$bee,$0$x$52$ca$,0$xdfa$5,0$xaea

c$,0$x$9$d$49,0$x$03$f$1,0$xeb$9$b$,0$xc$4$a$4\}$;

$/*$ SageMath Code $1($a$)$

$*/$

$//$ Update the sum here

const bigint$256$ add$\_$exp $=\{0\}$;

$/*$ SageMath Code $2($a$)$

$*/$

$//$ Update the difference here

const bigint$256$ sub$\_$exp $=\{0\}$;

const bigint$512$ mul$\_$exp $=$

$\{0$x$0095$ea$5$a$7,0$x$07$f$63$b$45$a$,0$x$0$c$91$ff$598,0$x$18$c$71$e$6$d$8,0$x$244$fa$7$f$13,0$x$28$f$2$eba$45,0$x$263$bdd$7$

$78,0$x$205$bef$01$a$,$

$0$x$18963$b$6$a$1,0$x$154$ed$05$bf$,0$x$1$b$81$ca$315,0$x$299508$e$38,0$x$36$ba$623$b$7,0$x$398$b$26$e$1$e$,0$x$3$f$4$c$64$d$71$

$,0$x$3$e$45$ae$57$b$,$

$0$x$3$fb$328$c$12,0$x$336181563,0$x$32$fec$692$a$,0$x$206882$c$5$c$,0$x$1$c$38$aa$08$c$,0$x$186558271,0$x$2039$d$413$f

$,0$x$1$c$9$efc$02$d$,$

$0$x$1$c$681$de$82,0$x$1$e$281238$d$,0$x$1$e$3534$cea,$0$x$0$b$07209$d$1,0$x$0$cc$4$dc$1$fe$,0$x$0$f$4028$c$5$e$,0$x$03$fbc$9028$

$,0$x$000000000\}$;

$//$ Print $256$ bit number $($Helper$)$

void bigint$256\_$print$($const bigint$256$ a$)\{$

int i;

printf$("\{")$;

for$($i $=0$; i $<15$; i$++)$

printf$("0$x$\%04$"PRIx$64",",$a$[$i$])$;

printf$("0$x$\%04$"PRIx$64"\}",$a$[$i$])$;

$\}$

$//$print $512$ bit number $($Helper$)$

void bigint$512\_$print$($const bigint$512$ a$)\{$

int i;

printf$("\{")$;

for$($i $=0$; i $<8$; i$++)$

printf$("0$x$\%09$"PRIx$64",",$a$[$i$])$;

printf$("$

$")$;

for$($i $=8$; i $<16$; i$++)$

printf$("0$x$\%09$"PRIx$64",",$a$[$i$])$;

printf$("$

$")$;

for$($i $=16$; i $<24$; i$++)$

printf$("0$x$\%09$"PRIx$64",",$a$[$i$])$;

printf$("$

$")$;

for$($i $=24$; i $<31$; i$++)$

printf$("0$x$\%09$"PRIx$64",",$a$[$i$])$;

printf$("0$x$\%09$"PRIx$64"\}",$a$[$i$])$;

$\}$

$//$ r $=$ a $+$ b

void add$256($bigint$256$ r$,$ const bigint$256$ a$,$ const bigint$256$ b$)\{$

int i;

uint$8\_$t carry $=0$;

$//$ Write $1$b here

$\}$

$//$ r $=$ a $-$ b

void sub$256($bigint$256$ r$,$ const bigint$256$ a$,$ const bigint$256$ b$)\{$

int i;

uint$8\_$t borrow $=0$;

$//$ Write $2$b here

$\}$

$//$ r $=$ a $*$ b using schoolbook method

void schoolbook$\_$mul$256($bigint$512$ r$,$ const bigint$256$ a$,$ const bigint$256$ b$)\{$

int i$,$ j;

$//$ Initialize r with $0$s

memset$($r$,0,256)$;

$//$ Write $3$b here

$\}$

$//$ r $=$ a $*$ b using comba method

void comba$\_$mul$256($bigint$512$ r$,$ const bigint$256$ a$,$ const bigint$256$ b$)\{$

int i$,$ j;

$//$ Write $3$c here

$\}$

$//$ r $=$ a $*$ b using Karatsuba method

void karatsuba$\_$mul$256($bigint$512$ r$,$ const bigint$256$ a$,$ const bigint$256$ b$)\{$

int i$,$ j;

$//$initialize arrays

uint$64\_$t ma$[8]$;

uint$64\_$t mb$[8]$;

uint$64\_$t z$0[16]=\{0\}$;

uint$64\_$t z$1[16]=\{0\}$;

uint$64\_$t z$2[16]=\{0\}$;